## Direct methods for sparse matrix solution

Curator: Iain Duff

Evgeni Sergeev

Jack Dongarra

Barbara Zubik-Kowal

Prof. Iain Duff , Rutherford Appleton Laboratory, Chilton, Oxfordshire, UK

Bora Uçar , CNRS and ENS Lyon, France

Direct methods for sparse matrix solutions are characterized by using a matrix factorization to solve a set of equations of the form

where \(b\) is a given vector, \(x\) is the vector of unknowns and \(A\) is a given sparse matrix representing the coefficients of unknowns in each equation. In contrast to iterative methods , direct methods obtain the solution to the above system in a finite and fixed number of steps.

In direct methods, the matrix \(A\) is factorized into a product of other sparse matrices. Systems of equations with the factor matrices as a coefficient matrix are very easy to solve.

## Factorization or decomposition

Depending on the properties of the matrix \(A\), different factorizations are used:

- For an \(n\times n\) symmetric positive definite matrix, the Cholesky factorization \(A=LL^T\) is usually computed, where \(L\) is a lower triangular (sparse) matrix. Often an \(LDL^T\) decomposition is used to avoid taking square roots and to avoid problems with matrices that are nearly singular.
- For a \(n\times n\) unsymmetric matrix \(A\), its LU decomposition \(A = LU\) is computed where \(L\) is a unit lower triangular matrix, and \(U\) is an upper triangular matrix.
- For an \(n\times n\) symmetric indefinite matrix, its \(LDL^T\) decomposition \(A = LDL^T\) is computed where \(D\) is a block diagonal matrix (with blocks of order 1 or 2), and \(L\) is a unit lower triangular matrix.
- For an \(m\times n\) rectangular matrix, with \(m\ge n\), its QR decomposition \(A=QR\) is computed. Here, \(Q\) is an \(m\times m\) orthogonal matrix, and \(R\) is an \(m\times n\) upper trapezoidal matrix.

## Cholesky factorization

Consider the sparse symmetric positive definite matrix

and its Cholesky factor \(L_A\) is given by (up to four units of accuracy)

Consider the permutation matrix

with its Cholesky factor \(L_B\)

## LU decomposition

## \(LDL^T\) decomposition

## QR decomposition

## Some other sparsity issues

## Computation schemes

- I. S. Duff and J. Koster, The design and use of algorithms for permuting large entries to the diagonal of sparse matrices, SIAM Journal on Matrix Analysis and Applications, 20(4), 889-901, 2001 ( doi ).
- A. George, Nested dissection of a regular finite element mesh, SIAM Journal on Numerical Analysis 10 (2): 345–363, 1973 ( doi ).
- S. Parter, The use of linear graphs in Gauss elimination, SIAM Review, 3(2), pp. 119-130, 1961 ( doi ).
- A. Pothen and C.-J. Fan, Computing the block triangular form of a sparse matrix, ACM Transactions on Mathematical Software, 16, pp. 303-324, 1990 ( doi ).
- D. J. Rose, Triangulated graphs and the elimination process, Journal of Mathematical Analysis and Applications, 32 (3), pp. 597-609, 1970 ( doi ).
- R. Schreiber, A New implementation of sparse Gaussian elimination, ACM Transactions on Mathematical Software, 8 (3), pp. 256--276, 1982 ( doi ).
- W. F. Tinney and J. W. Walker, Direct solutions of sparse network equations by optimally ordered triangular factorization, Proceedings of the IEEE, 55, pp. 1801–1809, 1967 ( doi ).
- M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM Journal on Algebraic and Discrete Methods, 2 (1), pp. 77-79, 1981 ( doi ).

## Recommended reading

- T. A. Davis, Direct Methods for Sparse Linear Systems , SIAM, Philadelphia, PA, 2006.
- I. S. Duff, A. M. Erisman, and J. K. Reid, Direct Methods for Sparse Matrices, Oxford University Press, London, 1986.
- I. S. Duff and B. Uçar, Combinatorial problems in solving linear systems, in Combinatorial Scientific Computing, U. Naumann and O. Schenk, eds., CRC Press, Boca Raton, FL, 2012, pp. 21–68.
- A. George and J. W. H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, Englewood Cliffs, N. J., 1981.
- J. W. H. Liu, The role of elimination trees in sparse factorization, SIAM Journal on Matrix Analysis and Applications, 11 (1), pp. 134--172, 1990 ( doi )
- Numerical Analysis
- Applied Mathematics

## Personal tools

## Focal areas

- Astrophysics
- Celestial mechanics
- Computational neuroscience
- Computational intelligence
- Dynamical systems
- More topics
- Recently published articles
- Recently sponsored articles
- Recent changes
- All articles
- List all Curators
- List all users
- Scholarpedia Journal
- What links here
- Related changes
- Special pages
- Printable version
- Permanent link

- This page was last modified on 31 March 2016, at 07:39.
- This page has been accessed 43,696 times.
- "Direct methods for sparse matrix solution" by Iain Duff and Bora Uçar is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License . Permissions beyond the scope of this license are described in the Terms of Use
- Privacy policy
- About Scholarpedia
- Disclaimers

- MATLAB Answers
- Community Home
- File Exchange
- Communities
- Treasure Hunt
- Virtual Badges
- MATLAB FAQs
- Contributors
- Recent Activity
- Flagged Content
- Manage Spam
- Trial software

You are now following this question

- You will see updates in your followed content feed .
- You may receive emails, depending on your communication preferences .

## How to solve a sparse matrix efficiently?

## Direct link to this question

https://www.mathworks.com/matlabcentral/answers/120850-how-to-solve-a-sparse-matrix-efficiently

## 5 Comments Show Hide 4 older comments

## Direct link to this comment

Sign in to answer this question.

## Answers (2)

## Direct link to this answer

## 0 Comments Show Hide -1 older comments

## 6 Comments Show Hide 5 older comments

- Thermal conduction (central differences)
- Enthalpy flow by mass flux (upwind scheme)
- Boundary conditions
- 3D geometry

## Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

You can also select a web site from the following list:

## How to Get Best Site Performance

- América Latina (Español)
- Canada (English)
- United States (English)
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- United Kingdom (English)

## Asia Pacific

## Sparse linear algebra ( scipy.sparse.linalg ) #

Abstract linear operators #, matrix operations #, matrix norms #, solving linear problems #.

Direct methods for linear equation systems:

Iterative methods for linear equation systems:

Iterative methods for least-squares problems:

## Matrix factorizations #

The svds function supports the following solvers:

Complete or incomplete LU factorizations

## IMAGES

## VIDEO

## COMMENTS

The six steps of problem solving involve problem definition, problem analysis, developing possible solutions, selecting a solution, implementing the solution and evaluating the outcome. Problem solving models are used to address issues that...

When multiplying or dividing different bases with the same exponent, combine the bases, and keep the exponent the same. For example, X raised to the third power times Y raised to the third power becomes the product of X times Y raised to th...

The four steps for solving an equation include the combination of like terms, the isolation of terms containing variables, the isolation of the variable and the substitution of the answer into the original equation to check the answer.

Data Structure for Sparse Matrix Reordering (cont.) ... (4) Solve (D-1 - H)z = -y.

One can factor the last block A_{KK} to find the corresponding entries in the unknown vector x, and then substitute those in the equations

Solving Linear Systems: Sparse Matrices, Iterative Methods ... Fill-in is a major problem for certain sparse matrices and leads to.

Problem definition. • Input. Problem definition. – Matrix A ... Takes advantage of sparse structure.

where A is an m x n matrix, b is given m-vector, and x is unknown solution n-vector to be determined. Such a system of equations asks question “Can vector b be.

Richard Peng (Georgia Tech)https://kyng.inf.ethz.ch/acseminar/2020-10-22_peng.htmlOctober 22, 2020.

The first of a series of 42 lectures on direct methods for sparse ... The Numerics of Solving Sparse Linear Systems Faster than Matrix

The solution to representing and working with sparse matrices is to use an alternate data structure to represent the sparse data. The zero

schemes for sparse matrices and some simple linear algebra operations using them.

As the upwind scheme is somewhat asymmetric, the sparse Matrix that looks like the one below. So far I use x = A\b, but when the problem starts to get

Compute a lower bound of the 1-norm of a sparse matrix. Solving linear problems#. Direct methods for linear equation systems: spsolve (A