linear_solver.cc revision 11420
12810Srdreslin@umich.edu/* 212500Snikos.nikoleris@arm.com * Copyright (c) 2015 ARM Limited 311051Sandreas.hansson@arm.com * All rights reserved 411051Sandreas.hansson@arm.com * 511051Sandreas.hansson@arm.com * The license below extends only to copyright in the software and shall 611051Sandreas.hansson@arm.com * not be construed as granting a license to any other intellectual 711051Sandreas.hansson@arm.com * property including but not limited to intellectual property relating 811051Sandreas.hansson@arm.com * to a hardware implementation of the functionality of the software 911051Sandreas.hansson@arm.com * licensed hereunder. You may use the software subject to the license 1011051Sandreas.hansson@arm.com * terms below provided that you ensure that this notice is replicated 1111051Sandreas.hansson@arm.com * unmodified and in its entirety in all distributions of the software, 1211051Sandreas.hansson@arm.com * modified or unmodified, in source code or in binary form. 1311051Sandreas.hansson@arm.com * 1411051Sandreas.hansson@arm.com * Redistribution and use in source and binary forms, with or without 1511051Sandreas.hansson@arm.com * modification, are permitted provided that the following conditions are 162810Srdreslin@umich.edu * met: redistributions of source code must retain the above copyright 172810Srdreslin@umich.edu * notice, this list of conditions and the following disclaimer; 182810Srdreslin@umich.edu * redistributions in binary form must reproduce the above copyright 192810Srdreslin@umich.edu * notice, this list of conditions and the following disclaimer in the 202810Srdreslin@umich.edu * documentation and/or other materials provided with the distribution; 212810Srdreslin@umich.edu * neither the name of the copyright holders nor the names of its 222810Srdreslin@umich.edu * contributors may be used to endorse or promote products derived from 232810Srdreslin@umich.edu * this software without specific prior written permission. 242810Srdreslin@umich.edu * 252810Srdreslin@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 262810Srdreslin@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 272810Srdreslin@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 282810Srdreslin@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 292810Srdreslin@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 302810Srdreslin@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 312810Srdreslin@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 322810Srdreslin@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 332810Srdreslin@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 342810Srdreslin@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 352810Srdreslin@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 362810Srdreslin@umich.edu * 372810Srdreslin@umich.edu * Authors: David Guillen Fandos 382810Srdreslin@umich.edu */ 392810Srdreslin@umich.edu 402810Srdreslin@umich.edu#include "sim/linear_solver.hh" 412810Srdreslin@umich.edu 4211051Sandreas.hansson@arm.comstd::vector <double> 4311051Sandreas.hansson@arm.comLinearSystem::solve() const 442810Srdreslin@umich.edu{ 4511051Sandreas.hansson@arm.com // Solve using gauss elimination, not ideal for big matrices 4611051Sandreas.hansson@arm.com std::vector < LinearEquation > smatrix = this->matrix; 4712349Snikos.nikoleris@arm.com 482810Srdreslin@umich.edu unsigned order = smatrix.size(); 492810Srdreslin@umich.edu for (unsigned row = 0; row < order - 1; row++) { 502810Srdreslin@umich.edu // Look for a non-zero row, and swap 512810Srdreslin@umich.edu for (unsigned i = row; i < order; i++) { 5211051Sandreas.hansson@arm.com if (smatrix[i][row] != 0.0f) { 532810Srdreslin@umich.edu if (i != row) { 542810Srdreslin@umich.edu LinearEquation tmp = smatrix[i]; 5511051Sandreas.hansson@arm.com smatrix[i] = smatrix[row]; 562810Srdreslin@umich.edu smatrix[row] = tmp; 5712724Snikos.nikoleris@arm.com } 5812724Snikos.nikoleris@arm.com break; 5912724Snikos.nikoleris@arm.com } 6012334Sgabeblack@google.com } 6112724Snikos.nikoleris@arm.com 6211051Sandreas.hansson@arm.com // Divide row by leading number to make it 1.0 6311051Sandreas.hansson@arm.com smatrix[row] *= (1.0f / smatrix[row][row]); 6411051Sandreas.hansson@arm.com 6511288Ssteve.reinhardt@amd.com // Add it (properly scaled) to the rows below 6612724Snikos.nikoleris@arm.com for (unsigned i = row + 1; i < order; i++) { 6713223Sodanrc@yahoo.com.br LinearEquation t = smatrix[row]; 6811051Sandreas.hansson@arm.com t *= -1.0f * smatrix[i][row]; 6912724Snikos.nikoleris@arm.com smatrix[i] = smatrix[i] + t; 7012724Snikos.nikoleris@arm.com } 7112724Snikos.nikoleris@arm.com } 7212724Snikos.nikoleris@arm.com 7311051Sandreas.hansson@arm.com // smatrix is now a triangular matrix with diagonal being 1 7411053Sandreas.hansson@arm.com // Just backproagate variable values from order-1 till 0 7511053Sandreas.hansson@arm.com std::vector <double> ret(order, 0.0f); 7612724Snikos.nikoleris@arm.com for (int row = order - 1; row >= 0; row--) { 7711051Sandreas.hansson@arm.com // Unknown value 7811051Sandreas.hansson@arm.com ret[row] = -smatrix[row][smatrix[row].cnt()] / smatrix[row][row]; 7911051Sandreas.hansson@arm.com // Propagate variable in the cnt term 8011051Sandreas.hansson@arm.com for (int i = row - 1; i >= 0; i--) { 8111601Sandreas.hansson@arm.com smatrix[i][smatrix[i].cnt()] += ret[row] * smatrix[i][row]; 8211601Sandreas.hansson@arm.com smatrix[i][row] = 0.0f; 8311051Sandreas.hansson@arm.com } 8412724Snikos.nikoleris@arm.com } 8511051Sandreas.hansson@arm.com 8612724Snikos.nikoleris@arm.com return ret; 8711600Sandreas.hansson@arm.com} 8811600Sandreas.hansson@arm.com