MATLAB Answers

How can I find out what algorithm mldivide is using?

87 views (last 30 days)
Raj on 28 Aug 2013
Commented: Jess on 1 Apr 2016
As I understand it, MATLAB's mldivide function uses a variety of algorithms to solve linear systems, performing various checks on the matrix involved to see what algorithm is applicable. These details are hidden from the user.
I recall that I have seen that there is some way to make MATLAB output the details of this procedure at runtime, where it prints out the result of the checks and the algorithm it decided on (LU, Cholesky, something from LAPACK even for sparse systems?). I can't find this information again despite my best attempts at searching these forums, the documentation, and the web. I know I have seen it somewhere. I was hoping someone here knows how to do this.
Failing this, can anyone tell me what algorithm mldivide would choose for the following? I have a pentadiagonal system in a sparse (2L x 2L) matrix for some whole number L
S = spdiags(myDiagonals,-2:2,2*L,2*L);
And a sparse right hand side with four nonzero entries.
b = spalloc(2*L,1,4);
Both contain complex entries in general and S it isn't symmetric or Hermitian or Toeplitz, but I'm not sure what other qualifiers might cause MATLAB to choose a specific algorithm. I calculate the inverse by
I appreciate any insights into what mldivide is doing in this case or how to get MATLAB to output the details of it's choice of algorithm. Thanks.

  1 Comment

Jess on 1 Apr 2016
You can tell MATLAB to output some of this information by running the following command before calling mldivide():

Sign in to comment.

Accepted Answer

Grzegorz Knor
Grzegorz Knor on 11 Dec 2013
See spparms function. For example:
A = sparse(diag(rand(5,1)))
sp\: bandwidth = 0+1+0.
sp\: is A diagonal? yes.
sp\: do a diagonal solve.
A = sparse(rand(10).*round(rand(10)-0.2));
porduces very long and detailed output:
sp\: bandwidth = 7+1+6.
sp\: is A diagonal? no.
sp\: is band density (0.35) > bandden (0.50) to try banded solver? no.
sp\: is A triangular? no.
sp\: is A morally triangular? no.
sp\: is A a candidate for Cholesky (symmetric, real positive diagonal)? no.
sp\: use Unsymmetric MultiFrontal PACKage with automatic reordering.
UMFPACK V5.4.0 (May 20, 2009), Control:
Matrix entry defined as: double
Int (generic integer) defined as: UF_long
0: print level: 2
1: dense row parameter: 0.2
"dense" rows have > max (16, (0.2)*16*sqrt(n_col) entries)
2: dense column parameter: 0.2
"dense" columns have > max (16, (0.2)*16*sqrt(n_row) entries)
3: pivot tolerance: 0.1
4: block size for dense matrix kernels: 32
5: strategy: 0 (auto)
6: initial allocation ratio: 0.7
7: max iterative refinement steps: 2
12: 2-by-2 pivot tolerance: 0.01
13: Q fixed during numerical factorization: 0 (auto)
14: AMD dense row/col parameter: 10
"dense" rows/columns have > max (16, (10)*sqrt(n)) entries
Only used if the AMD ordering is used.
15: diagonal pivot tolerance: 0.001
Only used if diagonal pivoting is attempted.
16: scaling: 1 (divide each row by sum of abs. values in each row)
17: frontal matrix allocation ratio: 0.5
18: drop tolerance: 0
19: AMD and COLAMD aggressive absorption: 1 (yes)
The following options can only be changed at compile-time:
8: BLAS library used: Fortran BLAS. size of BLAS integer: 8
9: compiled for MATLAB
10: CPU timer is ANSI C clock (may wrap around).
11: compiled for normal operation (debugging disabled)
computer/operating system: Microsoft Windows
size of int: 4 UF_long: 8 Int: 8 pointer: 8 double: 8 Entry: 8 (in bytes)
sp\: UMFPACK's factorization was successful.
sp\: However, UMFPACK may have failed to produce a correct factorization
possibly due to aggressive pivot tolerances or because the problem
is ill-conditioned.
sp\: These tolerances were:
Pivot Tolerance: 1.00e-01
Diagonal Pivot Tolerance: 1.00e-03
sp\: We will factor the matrix again but use standard partial pivoting.
sp\: UMFPACK's solve was successful.
UMFPACK V5.4.0 (May 20, 2009), Info:
matrix entry defined as: double
Int (generic integer) defined as: UF_long
BLAS library used: Fortran BLAS. size of BLAS integer: 8
MATLAB: yes.
CPU timer: ANSI clock ( ) routine.
number of rows in matrix A: 10
number of columns in matrix A: 10
entries in matrix A: 32
memory usage reported in: 16-byte Units
size of int: 4 bytes
size of UF_long: 8 bytes
size of pointer: 8 bytes
size of numerical entry: 8 bytes
strategy used: unsymmetric
ordering used: colamd on A
modify Q during factorization: yes
prefer diagonal pivoting: no
pivots with zero Markowitz cost: 1
submatrix S after removing zero-cost pivots:
number of "dense" rows: 0
number of "dense" columns: 0
number of empty rows: 1
number of empty columns 0
submatrix S not square or diagonal not preserved
symbolic factorization defragmentations: 0
symbolic memory usage (Units): 247
symbolic memory usage (MBytes): 0.0
Symbolic size (Units): 57
Symbolic size (MBytes): 0
symbolic factorization CPU time (sec): 0.00
symbolic factorization wallclock time(sec): 0.00
matrix scaled: yes (divided each row by sum of abs values in each row)
minimum sum (abs (rows of A)): 8.98358e-01
maximum sum (abs (rows of A)): 3.05977e+00
symbolic/numeric factorization: upper bound actual %
variable-sized part of Numeric object:
initial size (Units) 199 189 95%
peak size (Units) 978 947 97%
final size (Units) 33 30 91%
Numeric final size (Units) 124 116 94%
Numeric final size (MBytes) 0.0 0.0 94%
peak memory usage (Units) 1230 1199 97%
peak memory usage (MBytes) 0.0 0.0 97%
numeric factorization flops 1.65000e+02 3.60000e+01 22%
nz in L (incl diagonal) 27 16 59%
nz in U (incl diagonal) 37 29 78%
nz in L+U (incl diagonal) 54 35 65%
largest front (# entries) 49 12 24%
largest # rows in front 7 2 29%
largest # columns in front 7 6 86%
initial allocation ratio used: 0.7
# of forced updates due to frontal growth: 0
nz in L (incl diagonal), if none dropped 16
nz in U (incl diagonal), if none dropped 29
number of small entries dropped 0
nonzeros on diagonal of U: 9
min abs. value on diagonal of U: 0.00e+00
max abs. value on diagonal of U: 4.68e-01
estimate of reciprocal of condition number: 0.00e+00
indices in compressed pattern: 14
numerical values stored in Numeric object: 34
numeric factorization defragmentations: 1
numeric factorization reallocations: 1
costly numeric factorization reallocations: 1
numeric factorization CPU time (sec): 0.02
numeric factorization wallclock time (sec): 0.00
numeric factorization mflops (CPU time): 0.00
solve flops: 7.20000e+01
iterative refinement steps taken: 0
iterative refinement steps attempted: 0
solve CPU time (sec): 0.00
solve wall clock time (sec): 0.00
total symbolic + numeric + solve flops: 1.08000e+02


Sign in to comment.

More Answers (0)

Community Treasure Hunt

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

Start Hunting!