Left or right matrix division
The specific algorithm used for solving the simultaneous linear equations denoted by X = A\B and X = B/A depends upon the structure of the coefficient matrix A. To determine the structure of A and select the appropriate algorithm, MATLAB software follows this precedence:
If A is sparse and diagonal, X is computed by dividing by the diagonal elements of A.
If A is sparse, square, and banded, then banded solvers are used. Band density is (# nonzeros in the band)/(# nonzeros in a full band). Band density = 1.0 if there are no zeros on any of the three diagonals.
If A is real and tridiagonal, i.e., band density = 1.0, and B is real with only one column, X is computed quickly using Gaussian elimination without pivoting.
If the tridiagonal solver detects a need for pivoting, or if A or B is not real, or if B has more than one column, but A is banded with band density greater than the spparms parameter 'bandden' (default = 0.5), then X is computed using the Linear Algebra Package (LAPACK) routines in the following table.
Real | Complex | |
---|---|---|
A and B double | DGBTRF, DGBTRS | ZGBTRF, ZGBTRS |
A or B single | SGBTRF, SGBTRS | CGBTRF, CGBTRS |
If A is an upper or lower triangular matrix, then X is computed quickly with a backsubstitution algorithm for upper triangular matrices, or a forward substitution algorithm for lower triangular matrices. The check for triangularity is done for full matrices by testing for zero elements and for sparse matrices by accessing the sparse data structure.
If A is a full matrix, computations are performed using the Basic Linear Algebra Subprograms (BLAS) routines in the following table.
Real | Complex | |
---|---|---|
A and B double | DTRSV, DTRSM | ZTRSV, ZTRSM |
A or B single | STRSV, STRSM | CTRSV, CTRSM |
If A is a permutation of a triangular matrix, then X is computed with a permuted backsubstitution algorithm.
If A is symmetric, or Hermitian, and has real positive diagonal elements, then a Cholesky factorization is attempted. If A is found to be positive definite, the Cholesky factorization attempt is successful and requires less than half the time of a general factorization. Nonpositive definite matrices are usually detected almost immediately, so this check also requires little time.
If successful, the Cholesky factorization for full A is
A = R'*R
where R is upper triangular. The solution X is computed by solving two triangular systems,
X = R\(R'\B)
Computations are performed using the LAPACK routines in the following table.
Real | Complex | |
---|---|---|
A and B double | DLANSY, DPOTRF, DPOTRS, DPOCON | ZLANHE, ZPOTRF, ZPOTRS, ZPOCON |
A or B single | SLANSY, SPOTRF, SPOTRS, SDPOCON | CLANHE, CPOTRF, CPOTRS, CPOCON |
If A is sparse, then MATLAB software uses CHOLMOD to compute X. The computations result in
P'*A*P = R'*R
where P is a permutation matrix generated by amd, and R is an upper triangular matrix. In this case,
X = P*(R\(R'\(P'*B)))
If A is not sparse but is symmetric, and the Cholesky factorization failed, then MATLAB solves the system using a symmetric, indefinite factorization. That is, MATLAB computes the factorization P'*A*P=L*D*L', and computes the solution X by X=P*(L'\(D\(L\(P*B)))). Computations are performed using the LAPACK routines in the following table:
Real | Complex | |
---|---|---|
A and B double | DLANSY, DSYTRF, DSYTRS, DSYCON | ZLANHE, ZHETRF, ZHETRS, ZHECON |
A or B single | SLANSY, SSYTRF, SSYTRS, SSYCON | CLANHE, CHETRF, CHETRS, CHECON |
If A is Hessenberg, but not sparse, it is reduced to an upper triangular matrix and that system is solved via substitution.
If A is square and does not satisfy criteria 1 through 6, then a general triangular factorization is computed by Gaussian elimination with partial pivoting (see lu). This results in
A = L*U
where L is a permutation of a lower triangular matrix and U is an upper triangular matrix. Then X is computed by solving two permuted triangular systems.
X = U\(L\B)
If A is not sparse, computations are performed using the LAPACK routines in the following table.
Real | Complex | |
---|---|---|
A and B double | DLANGE, DGESV, DGECON | ZLANGE, ZGESV, ZGECON |
A or B single | SLANGE, SGESV, SGECON | CLANGE, CGESV, CGECON |
If A is sparse, then UMFPACK is used to compute X. The computations result in
P*(R\A)*Q = L*U
where
P is a row permutation matrix
R is a diagonal matrix that scales the rows of A
Q is a column reordering matrix.
Then X = Q*(U\L\(P*(R\B))).
If A is not square, then Householder reflections are used to compute an orthogonal-triangular factorization.
A*P = Q*R
where P is a permutation, Q is orthogonal and R is upper triangular (see qr). The least squares solution X is computed with
X = P*(R\(Q'*B))
If A is sparse, MATLAB computes a least squares solution using the sparse qr factorization of A.
If A is full, MATLAB uses the LAPACK routines listed in the following table to compute these matrix factorizations.
Real | Complex | |
---|---|---|
A and B double | DGEQP3, DORMQR, DTRTRS | ZGEQP3, ZORMQR, ZTRTRS |
A or B single | SGEQP3, SORMQR, STRTRS | CGEQP3, CORMQR, CTRTRS |
Note mldivide and mrdivide are not implemented for sparse matrices A that are complex but not square. |