What are efficient methods for solving A.x = b with a large sparse matrix?

  • Context: Graduate 
  • Thread starter Thread starter Zhivago
  • Start date Start date
  • Tags Tags
    Inversion Matrix
Click For Summary
SUMMARY

The discussion focuses on efficient methods for solving the equation A.x = b, where A is a large sparse matrix. The Biconjugate Gradient method is identified as a suitable approach, although alternatives such as random number methods and annealing techniques are suggested for potentially faster solutions. The participants also mention using LU decomposition, which is deemed too slow, and propose strategies like solving subsystems, block multiplication, and decomposing the matrix into symmetric and skew-symmetric parts to leverage the sparsity of A.

PREREQUISITES
  • Understanding of sparse matrix properties and representations
  • Familiarity with iterative methods for solving linear systems, specifically the Biconjugate Gradient method
  • Knowledge of LU decomposition and its computational implications
  • Basic concepts of matrix decomposition, including symmetric and skew-symmetric matrices
NEXT STEPS
  • Research the implementation of the Biconjugate Gradient method in numerical libraries such as SciPy
  • Explore randomized algorithms for solving linear systems, focusing on their efficiency with sparse matrices
  • Study block matrix multiplication techniques and their applications in solving large systems
  • Investigate methods for decomposing matrices into symmetric and skew-symmetric components
USEFUL FOR

This discussion is beneficial for data scientists, numerical analysts, and software engineers working with large-scale linear algebra problems, particularly those involving sparse matrices.

Zhivago
Messages
25
Reaction score
1
Hello everyone!

I need to find the vector x in the problem A.x = b
I have matrix A and vector b.
Inverting the matrix would do it, but in my case, the matrix is quite big. Luckily, it is extremelly sparse (lots of 0), so I guess there could be some way to take advantage of it.
The best approach I found is the Biconjugate Gradient method. Doing LU decomposition is too slow.
The exact answer is not needed. I only need to get x to a reasonable accurate result, so I think there could exist some methods using random numbers, annealing or something else faster than Biconjugate Gradient.
Someone has some ideas?

Best regards
 
Physics news on Phys.org
If it has a lot of zeroes, the simple school method could do: solve a subsystem and substitute the solution into the rest. Also block multiplication could be appropriate, depending on the matrix. Another idea is to split it into a symmetric and a skew symmetric part.
 

Similar threads

Graduate Solutions of Matrix Equation A X B^T = C
  • · Replies 1 ·
Replies
1
Views
3K
Graduate What is the next step after LU decomposition for solving Ax=b?
  • · Replies 5 ·
Replies
5
Views
2K
Graduate Solve Badly Scaled Problem with Newton-Chord Technique
  • · Replies 12 ·
Replies
12
Views
3K
Undergrad Rotation Matrix for Vector v=(a,b,c) by Angle θ | Efficient Computation Method
  • · Replies 4 ·
Replies
4
Views
2K
Graduate How to solve a very large overdetermined system numerically?
  • · Replies 1 ·
Replies
1
Views
3K
Graduate How to Efficiently Solve a Tridiagonal Matrix with Fringes?
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Linear least-squares method and row multiplication of matrix
  • · Replies 2 ·
Replies
2
Views
2K
Graduate Solving a large under-determined system of linear equations
  • · Replies 1 ·
Replies
1
Views
3K
Graduate Efficient Solution for (A+pI)x=b: Fast Matrix Inversion
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad Solving Ax=b; when to use LU decomposition?
  • · Replies 8 ·
Replies
8
Views
12K