linear_solver.hh revision 11420
111420Sdavid.guillen@arm.com/* 211420Sdavid.guillen@arm.com * Copyright (c) 2015 ARM Limited 311420Sdavid.guillen@arm.com * All rights reserved 411420Sdavid.guillen@arm.com * 511420Sdavid.guillen@arm.com * The license below extends only to copyright in the software and shall 611420Sdavid.guillen@arm.com * not be construed as granting a license to any other intellectual 711420Sdavid.guillen@arm.com * property including but not limited to intellectual property relating 811420Sdavid.guillen@arm.com * to a hardware implementation of the functionality of the software 911420Sdavid.guillen@arm.com * licensed hereunder. You may use the software subject to the license 1011420Sdavid.guillen@arm.com * terms below provided that you ensure that this notice is replicated 1111420Sdavid.guillen@arm.com * unmodified and in its entirety in all distributions of the software, 1211420Sdavid.guillen@arm.com * modified or unmodified, in source code or in binary form. 1311420Sdavid.guillen@arm.com * 1411420Sdavid.guillen@arm.com * Redistribution and use in source and binary forms, with or without 1511420Sdavid.guillen@arm.com * modification, are permitted provided that the following conditions are 1611420Sdavid.guillen@arm.com * met: redistributions of source code must retain the above copyright 1711420Sdavid.guillen@arm.com * notice, this list of conditions and the following disclaimer; 1811420Sdavid.guillen@arm.com * redistributions in binary form must reproduce the above copyright 1911420Sdavid.guillen@arm.com * notice, this list of conditions and the following disclaimer in the 2011420Sdavid.guillen@arm.com * documentation and/or other materials provided with the distribution; 2111420Sdavid.guillen@arm.com * neither the name of the copyright holders nor the names of its 2211420Sdavid.guillen@arm.com * contributors may be used to endorse or promote products derived from 2311420Sdavid.guillen@arm.com * this software without specific prior written permission. 2411420Sdavid.guillen@arm.com * 2511420Sdavid.guillen@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2611420Sdavid.guillen@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2711420Sdavid.guillen@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2811420Sdavid.guillen@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2911420Sdavid.guillen@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3011420Sdavid.guillen@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3111420Sdavid.guillen@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3211420Sdavid.guillen@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3311420Sdavid.guillen@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3411420Sdavid.guillen@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3511420Sdavid.guillen@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3611420Sdavid.guillen@arm.com * 3711420Sdavid.guillen@arm.com * Authors: David Guillen Fandos 3811420Sdavid.guillen@arm.com */ 3911420Sdavid.guillen@arm.com 4011420Sdavid.guillen@arm.com#ifndef __SIM_LINEAR_SOLVER_HH__ 4111420Sdavid.guillen@arm.com#define __SIM_LINEAR_SOLVER_HH__ 4211420Sdavid.guillen@arm.com 4311420Sdavid.guillen@arm.com#include <cassert> 4411420Sdavid.guillen@arm.com#include <sstream> 4511420Sdavid.guillen@arm.com#include <string> 4611420Sdavid.guillen@arm.com#include <vector> 4711420Sdavid.guillen@arm.com 4811420Sdavid.guillen@arm.com/** 4911420Sdavid.guillen@arm.com * This class describes a linear equation with constant coefficients. 5011420Sdavid.guillen@arm.com * The equation has a certain (variable) number of unkowns and it can hold 5111420Sdavid.guillen@arm.com * N+1 coefficients. 5211420Sdavid.guillen@arm.com */ 5311420Sdavid.guillen@arm.com 5411420Sdavid.guillen@arm.comclass LinearEquation { 5511420Sdavid.guillen@arm.com public: 5611420Sdavid.guillen@arm.com LinearEquation(unsigned unknowns) { 5711420Sdavid.guillen@arm.com eq = std::vector <double> (unknowns + 1, 0); 5811420Sdavid.guillen@arm.com } 5911420Sdavid.guillen@arm.com 6011420Sdavid.guillen@arm.com // Add two equations 6111420Sdavid.guillen@arm.com LinearEquation operator+ (const LinearEquation& rhs) { 6211420Sdavid.guillen@arm.com assert(this->eq.size() == rhs.eq.size()); 6311420Sdavid.guillen@arm.com 6411420Sdavid.guillen@arm.com LinearEquation res(this->eq.size() - 1); 6511420Sdavid.guillen@arm.com 6611420Sdavid.guillen@arm.com for (unsigned i = 0; i < res.eq.size(); i++) 6711420Sdavid.guillen@arm.com res.eq[i] = this->eq[i] + rhs.eq[i]; 6811420Sdavid.guillen@arm.com 6911420Sdavid.guillen@arm.com return res; 7011420Sdavid.guillen@arm.com } 7111420Sdavid.guillen@arm.com 7211420Sdavid.guillen@arm.com // Multiply the equation by a constant 7311420Sdavid.guillen@arm.com LinearEquation & operator*= (const double cnt) { 7411420Sdavid.guillen@arm.com for (auto & c: eq) 7511420Sdavid.guillen@arm.com c *= cnt; 7611420Sdavid.guillen@arm.com 7711420Sdavid.guillen@arm.com return *this; 7811420Sdavid.guillen@arm.com } 7911420Sdavid.guillen@arm.com 8011420Sdavid.guillen@arm.com // Access a certain equation coefficient 8111420Sdavid.guillen@arm.com double & operator[] (unsigned unkw) { 8211420Sdavid.guillen@arm.com assert(unkw < eq.size()); 8311420Sdavid.guillen@arm.com return eq[unkw]; 8411420Sdavid.guillen@arm.com } 8511420Sdavid.guillen@arm.com 8611420Sdavid.guillen@arm.com // Get a string representation 8711420Sdavid.guillen@arm.com std::string toStr() const { 8811420Sdavid.guillen@arm.com std::ostringstream oss; 8911420Sdavid.guillen@arm.com for (unsigned i = 0; i < eq.size(); i++) { 9011420Sdavid.guillen@arm.com if (i) 9111420Sdavid.guillen@arm.com oss << " + "; 9211420Sdavid.guillen@arm.com oss << eq[i]; 9311420Sdavid.guillen@arm.com if (i != eq.size() - 1) 9411420Sdavid.guillen@arm.com oss << "*x" << i; 9511420Sdavid.guillen@arm.com } 9611420Sdavid.guillen@arm.com oss << " = 0"; 9711420Sdavid.guillen@arm.com return oss.str(); 9811420Sdavid.guillen@arm.com } 9911420Sdavid.guillen@arm.com 10011420Sdavid.guillen@arm.com // Index for the constant term 10111420Sdavid.guillen@arm.com unsigned cnt() const { return eq.size() - 1; } 10211420Sdavid.guillen@arm.com 10311420Sdavid.guillen@arm.com private: 10411420Sdavid.guillen@arm.com 10511420Sdavid.guillen@arm.com /** Coefficients */ 10611420Sdavid.guillen@arm.com std::vector <double> eq; 10711420Sdavid.guillen@arm.com}; 10811420Sdavid.guillen@arm.com 10911420Sdavid.guillen@arm.comclass LinearSystem { 11011420Sdavid.guillen@arm.com public: 11111420Sdavid.guillen@arm.com LinearSystem(unsigned unknowns) { 11211420Sdavid.guillen@arm.com for (unsigned i = 0; i < unknowns; i++) 11311420Sdavid.guillen@arm.com matrix.push_back(LinearEquation(unknowns)); 11411420Sdavid.guillen@arm.com } 11511420Sdavid.guillen@arm.com 11611420Sdavid.guillen@arm.com LinearEquation & operator[] (unsigned eq) { 11711420Sdavid.guillen@arm.com assert(eq < matrix.size()); 11811420Sdavid.guillen@arm.com return matrix[eq]; 11911420Sdavid.guillen@arm.com } 12011420Sdavid.guillen@arm.com 12111420Sdavid.guillen@arm.com std::string toStr() const { 12211420Sdavid.guillen@arm.com std::string r; 12311420Sdavid.guillen@arm.com for (auto & eq: matrix) 12411420Sdavid.guillen@arm.com r += eq.toStr() + "\n"; 12511420Sdavid.guillen@arm.com return r; 12611420Sdavid.guillen@arm.com } 12711420Sdavid.guillen@arm.com 12811420Sdavid.guillen@arm.com std::vector <double> solve() const; 12911420Sdavid.guillen@arm.com 13011420Sdavid.guillen@arm.com private: 13111420Sdavid.guillen@arm.com std::vector < LinearEquation > matrix; 13211420Sdavid.guillen@arm.com}; 13311420Sdavid.guillen@arm.com 13411420Sdavid.guillen@arm.com#endif 135