The fastest algorithm for linear equations

[Ronankeating]

hi all,

Which is the fastest algorithm for linear equations in the form of A*X = B. Where A can be a symmetric or sparse matrix and also bear in mind that A matrix is huge in size something like 5000x5000.

Regards,

 

[Hurkyl]

Did you mean an algorithm to solve the equation for X? (and I assume B is a vector?)

Which algorithms are good depends immensely on the specific qualities of A and B, whatever prior knowledge you have about X, what field you're working in, and possibly even upon what sort of machine(s) you're using to solve it.

 

[Ronankeating]

Did you mean an algorithm to solve the equation for X? (and I assume B is a vector?)
Yes ,

None of the A or B matrices are optimized by any mean, the A matrix is global matrix which is been used for FEM in engineering to be specific triangular plate element 9 DOF.

I'm trying to solve that in Fortran .

 

[chiro]

Did you mean an algorithm to solve the equation for X? (and I assume B is a vector?)
Yes ,

None of the A or B matrices are optimized by any mean, the A matrix is global matrix which is been used for FEM in engineering to be specific triangular plate element 9 DOF.

I'm trying to solve that in Fortran .

I think what Hurkyl means is what you know about the operator A.

For example, do you know its determinant in advance? Is it triangular? Is it positive-definite?

Its these kinds of questions that you need to answer and then take it from there.

 

[Ronankeating]

chiro, thanks in advance

What I know about equation and A matrix is, it can be solved with Gauss elimination algorithm but it takes time cause matrix is huge. My purpose is to reduce that solution time. Since it can be solvable with Gauss elimination one thing for sure about A matrix is, it's not singular. I dont' know Gauss throughly or never such a need arised cause it neatly produced correct results so far.

Based on this fact I can only guess that A matrix is invertible, so the determinant can be calulated, but not sure whether it's positive definite or not.


Is there any occasions where Gauss elimination fails with the solution with such a large matrix?

Regards,

 

[HallsofIvy]

You might want to look at
http://web.eecs.utk.edu/~dongarra/etemplates/node388.html
http://reference.wolfram.com/mathematica/howto/WorkWithSparseMatrices.html

 

[Ronankeating]

ok thanks,

I already tried the LU decomposition this reduces the solution time approx 1/3 of Gauss method.

One question stuck in my mind do any of these algortihms deviates or causing the round-off error during solution if the matrix is huge?

 

[chiro]

ok thanks,

I already tried the LU decomposition this reduces the solution time approx 1/3 of Gauss method.

One question stuck in my mind do any of these algortihms deviates or causing the round-off error during solution if the matrix is huge?

Thats got more to do with things like the determinant than say the size of the matrix.

There is a whole subject devoted to this based on things like condition numbers and matrix norms if you are interested.

 

[AlephZero]

If you are doing linear structural mechanics with FEM, your matrices will be symmetric and postiive definite (after you constrain the structure). Those properties mean you don't have to worry about taking special precautions to preserve numerical accuracy. If the condition number of the matrix is poor you will lose some accuracy but you can't do anything much about that. So long as you do 64-bit arithmetic (not 32-bit) that shouldn't be a problem.

If you have got an LU decomposition solver working, and your matrix has a typical structure from an FE mesh you can probably speed it up considerably just by skipping the numerical calculations that do nothing. For eaxmple when the "inside" do-loop in the factorization does an operation like

(Row i) = (Row i) + factor * (Row j)

check if factor = 0 before you do the loop!

One subset of sparse solution methods is based on exploiting that simple idea to the maximum extent, but for your relatively small model size (5000 DOF) just doing that simple test will probably make a big difference.

If you move to bigger problems where the "full" system matrix is too big to fit in RAM on your computer, that's the time to start using one of the equation solver packages in the earlier posts.