Solving sparse systems: Difference between revisions

Revision as of 17:55, 15 March 2017

There are many methods available for solving sparse systems. We compare some of them here.

Mathematica has the following methods available (https://reference.wolfram.com/language/ref/LinearSolve.html#DetailsAndOptions)

direct: banded, cholesky, multifrontal (direct sparse LU)
iterative: Krylov

Matlab has the following methods:

direct: https://www.mathworks.com/help/matlab/ref/mldivide.html#bt42omx_head
iterative: https://www.mathworks.com/help/matlab/math/systems-of-linear-equations.html#brzoiix, including bicgstab, gmres

Eigen has the following methods: (https://eigen.tuxfamily.org/dox-devel/group__TopicSparseSystems.html)

direct: sparse LU
iterative: bicgstab, cg

Solving a simple sparse system $A x = b$ with $A = \begin{bmatrix} 1 & -2 & \\ 1 & \ddots & \ddots \\ & \ddots & \end{bmatrix}$ and $b = \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}$ with dimension $n$ has the following timings in seconds:

$n = 10^6$	Matlab	Mathematica	Eigen
Banded		2.86	/
	/	1.73	0.78
Bicgstab / Krylov	19.32	3.92

@@ Line 13: / Line 13: @@
 * iterative: bicgstab, cg
-Solving a simple sparse system $A x = b$ with $A = \begin{bmatrix}  1 & 1 & \\ 1 & \ddots & \ddots \\ & \ddots & \end{bmatrix}$ and $b = \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}$ with dimension $n$
+Solving a simple sparse system $A x = b$ with $A = \begin{bmatrix}  1 & -2 & \\ 1 & \ddots & \ddots \\ & \ddots & \end{bmatrix}$ and $b = \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}$ with dimension $n$
-has the following timings:
+has the following timings in seconds:
 {| class="wikitable"
 |-
+! $n = 10^6$
 ! Matlab
 ! Mathematica
 ! Eigen
 |-
-! Row header 1
+! Banded
-| row 1, cell 2
+|
-| row 1, cell 3
+| 2.86
+| /
 |-
-! Row header 2
+!
-| row 2, cell 2
+| /
-| row 2, cell 3
+| 1.73
+| 0.78
+|-
+! Bicgstab / Krylov
+| 19.32
+| 3.92
+|
 |}