# Solving linear equation systems including sparse matrices

• 11-24-2012, 07:03 PM
GregXel
Solving linear equation systems including sparse matrices
Hi everyone,

Working on a Java project, I face the following problem:

I would like to solve a linear equation system of the form

A * x = b.

Therein, the matrix ‘A’ and both vectors ‘x’ and ‘b’ contain several thousand array elements. ‘A’, however, is a sparse matrix and only a small number of diagonals of ‘A’ may contain values that differ from zero.

The use of Java standard solvers results in very long computation times as these solvers normally do not use the specific properties of sparse matrices. Therefore I would like to ask if someone knows packages that include linear equation solvers which are able to solve systems as described above in a reasonable time.

I would be very grateful for any hint.

Thanks a lot in advance and best regards
• 11-24-2012, 07:21 PM
JosAH
Re: Solving linear equation systems including sparse matrices
Perform a LUP decomposition on A, i.e. L*U == P*A --> L*U*b == P*A*b --> Pt*L*U*b is what you're looking for (Pt is the transposed of row permutation matrix P). Lef multiplying by U is A simple backward substitution and multiplying b L is a forward substitution. If A is sparse then both L and U are also sparse. Matrix P can be stored as a single one dimensional array of index values. Google is your friend here.

kind regards,

Jos
• 11-24-2012, 08:05 PM
doWhile
Re: Solving linear equation systems including sparse matrices
• 11-25-2012, 12:54 PM
DarrylBurke
Re: Solving linear equation systems including sparse matrices
• 11-26-2012, 12:15 PM
JosAH
Re: Solving linear equation systems including sparse matrices
Too bad about all those cross postings because keeping those L and U matrixes sparse is an interesting problem ...

kind regards,

Jos