Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Sparse linear system
Replies: 14   Last Post: May 21, 2010 9:47 AM

 Messages: [ Previous | Next ]
 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 600-800.

>
> > > 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_{t-1} - grad(F(X_{t-1}))
>
> > 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.

Date Subject Author
5/19/10 luca
5/19/10 luca
5/19/10 Torsten Hennig
5/19/10 Torsten Hennig
5/19/10 luca
5/19/10 luca
5/19/10 Fred Krogh
5/19/10 Chip Eastham
5/20/10 Fred Krogh
5/20/10 Chip Eastham
5/20/10 luca
5/21/10 Chip Eastham
5/19/10 Chip Eastham
5/20/10 luca
5/20/10 Peter Spellucci