The fastest algorithm for linear equations

In summary, the conversation discusses the best algorithm for solving linear equations in the form of A*X = B, where A is a symmetric or sparse matrix with a size of 5000x5000. The participants mention different algorithms, such as Gauss elimination and LU decomposition, and discuss their advantages and potential for round-off errors. They also mention the importance of considering the properties of the matrix, such as its determinant and condition number, and mention the use of equation solver packages for larger problems.
  • #1
Ronankeating
63
0
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,
 
Physics news on Phys.org
  • #2
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.
 
  • #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 .
 
  • #4
Ronankeating said:
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.
 
  • #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?

Regards,
 
  • #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?
 
  • #8
Ronankeating said:
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.
 
  • #9
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.
 

1. What is an algorithm for linear equations?

An algorithm for linear equations is a set of steps or rules used to solve any linear equation, which is an equation with one or more variables raised to the first power and no terms with different powers. It is a mathematical formula used to find the values of the variables in the equation.

2. How does the fastest algorithm for linear equations work?

The fastest algorithm for linear equations, also known as the Gaussian elimination algorithm, works by using a series of operations (such as adding, subtracting, and multiplying) to simplify the equation and solve for the variables. It involves reducing the equation to its simplest form, known as the echelon form, and then back-substituting to find the values of the variables.

3. What makes an algorithm the fastest for solving linear equations?

An algorithm is considered the fastest for solving linear equations when it requires the fewest number of operations to solve the equation. This can be achieved by using efficient methods such as pivoting, which involves swapping rows of the equation to simplify it, and using elimination techniques to reduce the number of operations needed.

4. Is the fastest algorithm for linear equations always the most accurate?

No, the fastest algorithm for linear equations may not always be the most accurate. While it is designed to solve equations quickly, it may not work for certain types of equations or may produce less accurate results compared to other algorithms. It is important to consider the type of equation and the precision needed when choosing an algorithm.

5. Can the fastest algorithm for linear equations be used for all types of equations?

No, the fastest algorithm for linear equations is specifically designed for solving linear equations. It may not work for other types of equations, such as quadratic or exponential equations. Each type of equation may require a different algorithm or method for solving it accurately and efficiently.

Similar threads

  • Linear and Abstract Algebra
Replies
8
Views
993
  • Linear and Abstract Algebra
Replies
6
Views
755
  • Linear and Abstract Algebra
Replies
1
Views
992
  • Linear and Abstract Algebra
Replies
4
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
878
  • Linear and Abstract Algebra
Replies
8
Views
770
  • Linear and Abstract Algebra
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
977
Replies
7
Views
782
Replies
27
Views
1K
Back
Top