What's the best way to solve a linear system? Backslash is simple, but the factorization it computes internally can't be reused to solve multiple systems (x=A\b then y=A\c). You might be tempted to use inv(A), as S=inv(A) ; x=S*b ; y=S*c, but's that's slow and inaccurate. The best solution is to use a matrix factorization (LU, CHOL, or QR) followed by forward/backsolve, but figuring out the correct method to use is not easy.
In textbooks, linear algebraic expressions often use the inverse. For example, the Schur complement is written as S=A-B*inv(D)*C. It is never meant to be used that way. S=A-B*(D\C) or S=A-(B/D)*C are better, but the syntax doesn't match the formulas in your textbook.
The solution is to use the FACTORIZE object. It overloads the backslash and mtimes operators (among others) so that solving two linear systems A*x=b and A*y=c can be done with this:
F=factorize(A) ;
x=F\b ;
y=F\c ;
An INVERSE method is provided which does not actually compute the inverse itself (unless it is explicitly requested). The statements above can be done equivalently with this:
S=inverse(A) ;
x=S*b ;
y=S*c ;
That looks like a use of INV(A), but what happens is that S is a factorized representation of the inverse of A, and multiplying S times another matrix is implemented with a forward/backsolve.
Wiith the INVERSE function, your Schur complement computation becomes S = A - B*inverse(D)*C which looks just like the equation in your book ... except that it computes a factorization and then does a forward/backsolve, WITHOUT computing the inverse at all.
An extensive demo is included, as well as a simple and easy-to-read version (FACTORIZE1) with fewer features, as an example of how to create objects in MATLAB.
If the system is over-determined, QR factorization is used to solve the least-squares problem. If the system is under-determined, the transpose of A is factorized via QR, and the minimum 2-norm solution is found. In MATLAB, x=A\b finds a "basic" solution to an under-determined system.
You can compute a subset of the entries of the inverse just by referencing them. For example, S=inverse(A), S(n,n) computes the (n,n) entry of the inverse, without computing all of them.
In the RARE case that you need the entire inverse (or pseduo-inverse of a full-rank rectangular matrix) you can force the object to become "double", with S = double (inverse (A)). This works for both full and sparse matrices (pinv(A) only works for full matrices).
And remember ... don't ever multiply a matrix by inv(A).
This code is published as "Algorithm 930: FACTORIZE: an object-oriented linear system solver for MATLAB", T. A. Davis, ACM Transactions on Mathematical Software, Vol 39, Issue 4, pp. 28:1 - 28:18, 2013. |