Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The fastest algorithm for linear equations

  1. Feb 24, 2012 #1
    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.

  2. jcsd
  3. Feb 25, 2012 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
  4. Feb 25, 2012 #3
    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 .
  5. Feb 25, 2012 #4


    User Avatar
    Science Advisor

    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.
  6. Feb 25, 2012 #5
    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?

  7. Feb 25, 2012 #6


    User Avatar
    Science Advisor

  8. Feb 25, 2012 #7
    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?
  9. Feb 25, 2012 #8


    User Avatar
    Science Advisor

    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.
  10. Feb 25, 2012 #9


    User Avatar
    Science Advisor
    Homework Helper

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook