Introduction to Sparse Linear System

Sparse solver concept

All the solvers have the same general concepts and follow a pre-defined set of rules, as given in the syntax below. 

#include <Eigen/RequiredModuleName>
  // ...
  SparseMatrix<double> matrix;
  // Firstly fill the Matrix named ‘matrix’
  VectorXd vector, x;
  // Then fill the Matrix named ‘vector’
  // Matrix*x = vector; solve the problem now
  SolverClassName<SparseMatrix<double> > solver;
  solver.compute(matrix);
  if(solver.info()!=Success) {
   // We calculate the information and check if it is a success or not
  return;
}
  x = solver.solve(vector);
  if(solver.info()!=Success) {
   // Here also, the solving has failed
   return;
}
  // solve for another right hand side:
  matrix1 = solver.solve(vector1);

In the above example, we are solving for both triangles however, with SPD solvers, we are given the option to choose which part of the triangular matrix we want to choose. Like In the below example, we have chosen only the upper triangular part of the input matrix A. The opposite triangle might either will have arbitrary values or be empty.

#include <Eigen/IterativeLinearSolvers>
  ConjugateGradient<SparseMatrix<double>, Eigen::Upper> solver;
  // solving for value of x
  x = solver.compute(matrix).solve(vector); 

The Compute Step

Here, we factorize the matrix as

1. LLT for self-adjoint matrices
2. LDLT for general hermitian matrices
3. LU for non-hermitian matrices
4. QR for rectangular matrices. 

For direct solver class, the compute step is further subdivided into 

analyzePattern(): Used to reorder the non-zero elements of the matrix, so that the factorization step creates less fill-in. This step is ran every time the values of the matrix change, without changing structural pattern. For example: 

DirectSolverClassName<SparseMatrix<double>, OrderingMethod<IndexType> > solver;

factorize(): Here, the factors of the coefficient matrix are computed. For example:

IterativeSolverClassName<SparseMatrix<double>, PreconditionerName<SparseMatrix<double> > solver;

The Solve step

The solve() function is used to solve the problem of linear equations with one or many right-hand sides.

RHS = solver.solve(matrix);

B can be a matrix or vector where the columns form the different right-hand sides. The solve() function can be called several times, for instance, when all the right-hand sides are only available at once.

rhs1 = solver.solve(matrix1);
// It is used to solve for the second right hand side b2
rhs2 = solver.solve(matrix2);
//  ...

For direct methods, the solution is computed at the machine's precision. Sometimes, the solution needs to be more accurate. In this case, the iterative methods are better suited, and the desired accuracy can be set before the solve step by using setTolerance().

BenchmarkRoutine

Most of the time, we want to know how much time it will take to solve the problem on your system.Eigen can do this task for us and tell us about the solve time, compute tim, compute time or errors during iteration. We give a benchmark routine that can be utilized for this purpose. To use it, navigate to bench/spbench> compile the routine by typing make spbenchsolver.> Run it with the --help option to get the list of all options. The routine shows back the statistics from all solvers in Eigen.

Frequently Asked Questions

What is a sparse function?

The SPARSE function changes a matrix that have multiple zeros into a matrix stored in a sparse format which is better for use with the ITSOLVER call or the SOLVELIN call.

Where is the sparse matrix used?

Sparse matrices are used in specific ways in computer science and have different data analysis and storage protocols and techniques related to their use.

How are eigenvectors used?

Eigenvectors are used to make linear transformation understandable. Think of eigenvectors as stretching/compressing an X-Y line chart without changing their direction.

Conclusion

In this article, we learned the basic method to linear problems with the help a of C++ library called Eigen. We also learned to list of parse solvers, the compute step, solve step and benchmark routines. 

Please refer to our guided pathways on Code studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Please vote 🏆 our blogs if you find them helpful and informative!

Happy coding🤗