luca
Posts:
11
Registered:
5/19/10


Re: Sparse linear system
Posted:
May 20, 2010 5:08 AM


On 20 Mag, 05:36, Chip Eastham <hardm...@gmail.com> wrote: > On May 19, 10:22 am, luca <luca.frammol...@gmail.com> wrote: > > > > > > > On 19 Mag, 12:07, luca <luca.frammol...@gmail.com> wrote: > > > > Hi, > > > > suppose i have a matrix M X N of reals. This matrix is sparse. Every > > > row has only 3 non zero values (they are always 1, 2, 1). The M and > > > N are on the order of 600800. > > > > Is there a fast library (way) to solve a sparse linear system A X = B, > > > where the matrix A is of the type defined below?? > > > > I need a library writte in C/C++ that is possibly portable. > > > > Thank you, > > > Luca > > > A is a NxN real sparse symmetric matrix. Sorry for the confusion. I > > will give you guys more details. The problem i am facing is the > > following. Given a NxN real sparse symmetric matrix A, solve the > > following system of linear equation: > > > (A + aI)X_{t} = aX_{t1}  grad(F(X_{t1})) > > > where <a> is a real scalar (the step size), X_{t} is a vector of N > > reals, F is differentiable function, I is the identity matrix. > > One start with an arbitrary X_0 and <a> = some constant and every > > iteration involves the solution of this system of linear equations and > > the update of the scalar <a> using some schedule. > > > Since A is a big sparse matrix, A+aI is a big sparse matrix too. So i > > could use a LU factoriztion of A+aI and than solve > > the system in the usual way. > > > A does not change during the iterations, but the coefficient matrix is > > A+aI, so i need to compute the LU of A+aI. > > I would really like to avoid the LU factorization at every iteration, > > but i don't see any alternative. Maybe there is a way > > to compute LU of A and than, given aI, compute (in a fast way) the LU > > of A+aI using the LU of A... > > > So, what i need is a free portable C/C++ code for computing a fast LU > > factorization of a sparse matrix. > > > Thank you, > > Luca > > > So, > > Is the matrix A tridiagonal? You suggested as much > when you said the nonzero entries were 1, 2, 1. > Also is a > 0 ? > > regards, chip Nascondi testo citato > >  Mostra testo citato 
The matrix A come from the multiplication of one other matrix K with its transpose: A = K^T * K, where K^T means the transpose of K. K is also a big and sparse reak matrix M x N. K has only three non zero elements (1,2,1) per row.

