Reputation: 1972
I wish to solve a general system of linear equations A*x=b. The m-by-m matrix is sparse, real, square, somewhat poorly-conditioned, non-symmetric, but it is singular (rank(A)==m-1) because x
is known only up to an additive constant.
I can create the matrix A by specifying its nonzero entries in three vectors (i
, j
, and v
) such that A(i(k),j(k)) = v(k)
:
A = sparse( i, j, v, m, m );
I can solve this original equation as follows:
x = A \ b;
If I want a unique solution, I can impose a constraint (say, x(4) == 3.14159) after calculating the non-unique solution:
x = x - x(4) + 3.14159;
I can make a new, full-rank matrix C
by adding an additional uniqueness constraint, as follows:
% Add the constraint x(4) == 3.14159
extraRow = zeros(1,m);
extraRow(4) = 1.0;
C = [A; extraRow]; % Add to the matrix A
d = [b; 3.14159]; % Add to the RHS vector, b
% Solve C*y = d for y
y = C \ d;
I understand that when I solve these equations via either x = A \ b
or y = C \ b
, MATLAB interprets the \
as the mldivide()
command (link), which runs some tests on the matrix and figures out an optimal algorithm to solve the routine (see link for details).
These details are made verbose at runtime by setting MATLAB's sparse matrix solving parameters via spparms('spumoni',2)
When I compute x
and/or y
, I notice the following:
Both UMFPACK and SuiteSparseQR are part of the SuiteSparse software package (link).
(Somewhat unexpectedly, solving the modified equation gives more error than the original equation. While significant, this error is still at an acceptably-low threshold.)
Now that I can solve this problem in MATLAB, I wish to do so in Fortran. Unfortunately, MATLAB's mldivide()
command is a black-box in that I cannot see how it sets up or calls the SuiteSparse routines.
Given that I have the three sparse vectors in Fortran (90+) as shown below, how can I solve the problem using SuiteSparse?
Alternatively, does anyone know of any F90 wrapper routines that interface to UMFPACK to make this easier?
I'm more than happy if anyone can help with this--either with the Original Equation or with the Modified Equation. (If you help with one, I could probably get the other.)
subroutine solveSparseMatrixEqnViaSuiteSparse( m, n, nnz, i, j, v, x )
implicit none
integer, intent(in) :: m ! sparse matrix rows
integer, intent(in) :: n ! sparse matrix columns
integer, intent(in) :: nnz ! number of nonzero entries
integer, dimension(1:nnz), intent(in) :: i ! row indices of nonzero entries
integer, dimension(1:nnz), intent(in) :: j ! column indices of nonzero entries
real*8, dimension(1:nnz), intent(in) :: v ! values of nonzero entries
real*8, dimension(1:n), intent(out) :: x ! solution vector
! I have no idea what to do next!
end function solveSparseMatrixEqnViaSuiteSparse
What confuse me are the following:
Note: Although I'm asking this question with a particular problem in mind (who isn't!?), I believe this is general enough to be useful to others as well.
Upvotes: 18
Views: 1713
Reputation: 1544
Two things here. First, for examples calling UMFPACK in fortran/C, please checkout the source code in one of my projects, for example,
https://github.com/fangq/blit/blob/master/src/blit_ilupcond.f90#L156-L162
here I am call umfpack from fortran90 using a umf4_f77wrapper.c unit
https://github.com/fangq/blit/blob/master/src/umf4_f77wrapper.c
Secondly, regarding the back-slash operator, it is essentially solving the Moore-Penrose pseudo-inversion problem to get a least-square solution, see
https://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_inverse
basically, any matrix equation A*x=b (including under-determined - size(A,1)<size(A,2) - or overdetermined - size(A,1)>size(A,2) - problems), solving x=A\b
is the same as solving
(A'A) x = A'b
=> x=inv(A'A)*A'b
however, you don't solve the right-equation by taking an inversion, but apply a linear solver solving the left equation (A'A)x=A'b
you can also apply the Sherman–Morrison–Woodbury formula to construct a equivalent, but more compact, solution when the original equation is under-determined, which is x=A'*inv(A'A)*b
https://en.wikipedia.org/wiki/Woodbury_matrix_identity
Upvotes: 0