Re: Reducing calculation time for solving linear equation system

Peter Spellucci wrote:
In article <1168871832.240981.165510@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"Diaboflo" <flohudelist@xxxxxx> writes:
>Hi,
>I have a quite large system of linear equations to solve (Ax=b). For my
>simulations this step has to be done several hundred times for similar
>matrices. The matrix is quite empty (most elements = 0) and I could
>separate this problems into a few smaller matrices which would reduce
>the number of elements (eliminate all elements = 0).

I wonder how this could be done if not the system is already quite
special, and, of course, the matrix reducible i.e. afer a permutation
of rows and columns of the form
[A11 , A12,..,A1n; O A22 , A23 ,...A2n; O O A33 .... ; O...O Ann ];
with he Aij Matrices and the Aii quadratic.

It is an inhomogenious set of linear equations. The equations are not
reducible.
I can seperate the matrix into several smaller square matrices and
solving them one after each other, using the results of the submatrix
before.
The rank of the matrix is M*N which can be splitted up into N matrices
of rank M.

>To solve the problem I use the NAG function f04adf which solves the
>system as followed:
>
>Given a set of complex linear equations AX = B, the routine first
>computes an LU factorization of A with
>partial pivoting, PA = LU, where P is a permutation matrix, L is lower
>triangular and U is unit upper
>triangular. The columns x of the solution X are found by forward and
>backward substitution in Ly = Pb
>and Ux = y, where b is a column of the right-hand side matrix B.
>
>Do I save calculation time by splitting up the problem into many small
>ones? Is there a way to find out how remarkable the difference is?

if you use standard lu and not any sparse matrix code
then the diffewrence can be enormous:
say you have originally 1000 equations and can break this up into
4 systems of dimnsion 250 the effort changes from about
2*10^9/3 operations to about 4*10^7 operations (multiplication and additions)
and if the splitting becomes even finer the effect becomes more and more
tremendous. (without any additional structure LU takes about 2*n^3/3 operations)
hth
peter


That sounds like it is worth doing some optimisation to this method!
Thanks for your help!



Thanks,
Florian


.

Relevant Pages