Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Boost's Linear Algebra Solution for y=Ax

Does boost have one? Where A, y and x is a matrix (sparse and can be very large) and vectors respectively. Either y or x can be unknown.

I can't seem to find it here: http://www.boost.org/doc/libs/1_39_0/libs/numeric/ublas/doc/index.htm

like image 687
neversaint Avatar asked Aug 04 '09 01:08

neversaint


People also ask

How do you find the particular solution of Ax B?

One way to find a particular solution to the equation Ax = b is to set all free variables to zero, then solve for the pivot variables. The general solution to Ax = b is given by xcomplete = xp + xn, where xn is a generic vector in the nullspace.

How many solutions does the homogeneous system Ax 0⃗ of linear equations have?

Corollary 1.3 Let A be an m × n matrix. A homogeneous system of equations Ax = 0 will have a unique solution, the trivial solution x = 0, if and only if rank[A] = n. In all other cases, it will have infinitely many solutions.


3 Answers

yes, you can solve linear equations with boost's ublas library. Here is one short way using LU-factorize and back-substituting to get the inverse:

using namespace boost::ublas;

Ainv = identity_matrix<float>(A.size1());
permutation_matrix<size_t> pm(A.size1());
lu_factorize(A,pm)
lu_substitute(A, pm, Ainv);

So to solve a linear system Ax=y, you would solve the equation trans(A)Ax=trans(A)y by taking the inverse of (trans(A)A)^-1 to get x: x = (trans(A)A)^-1Ay.

like image 138
Inverse Avatar answered Oct 30 '22 18:10

Inverse


Linear solvers are generally part of the LAPACK library which is a higher level extension of the BLAS library. If you are on Linux, the Intel MKL has some good solvers, optimized both for dense and sparse matrices. If you are on windows, MKL has a one month trial for free... and to be honest I haven't tried any of the other ones out there. I know the Atlas package has a free LAPACK implementation but not sure how hard it is to get running on windows.

Anyways, search around for a LAPACK library which works on your system.

like image 36
DeusAduro Avatar answered Oct 30 '22 16:10

DeusAduro


One of the best solvers for Ax = b, when A is sparse, is Tim Davis's UMFPACK

UMFPACK computes a sparse LU decomposition of A. It is the algorithm that gets used behind the scenes in Matlab when you type x=A\b (and A is sparse and square). UMFPACK is free software (GPL)

Also note if y=Ax, and x is known, but y is not, you compute y by performing a sparse matrix vector multiply, not by solving a linear system.

like image 37
codehippo Avatar answered Oct 30 '22 18:10

codehippo