# Solving very large matrices in “pieces”

Say you have a very dense matrix that is 30000x30000 elements. The very dense matrix comes from the radiosity equation, which I discussed here.

Say you have Ax = B. You have B, and A is 30000x30000 elements. Solving: You need to find x given B.

Solving a matrix like this in C code actually introduces an interesting problem: you cannot actually store it all in memory at once.

So, I want to know about ways to solve this problem "in pieces" -- I want to mathematically decompose the 30000x30000 matrix into smaller sub-matrices (perhaps in chunks of 30000x20?), and somehow solve that way.

What algorithms exist to break down / solve a matrix "in pieces" or steps, that can be solved regardless of memory restrictions? It can be an iterative technique.

-
Could you clarify 'Solving'? Is it finding determinants, or adding, or multiplying, or inverting? –  KalEl Aug 18 '10 at 20:24
Please consider posting this on StackOVerflow. This might be off-topic here. In any case, in the current state your question is liable to be closed as 'not a real question' as you haven't specified what 'solving' means. –  Aryabhata Aug 18 '10 at 20:32
The techniques are typically just called "block" methods. If you have a 64 bit processor (so you can address the 7gigs of ram for A), then you can just use an off the shelf solver. If you can write a function that multiplies a vector by A (whether or not you actually have the entries of A in memory somewhere), then there are many efficient iterative solvers. –  Jack Schmidt Aug 18 '10 at 22:40
Also, is the matrix dense or sparse? This makes a big difference. The problem is likely intractable if dense. –  Noldorin Aug 18 '10 at 22:47
Otherwise, the only other observation I can make is that if all the eigenvalues of $\mathbf{P}\mathbf{F}$ are less than 1 in magnitude, you can expand the inverse of your matrix $\mathbf{I}-\mathbf{P}\mathbf{F}$ as a geometric series in $\mathbf{P}\mathbf{F}$: $\mathbf{I}+\mathbf{P}\mathbf{F}+\mathbf{P}^2\mathbf{F}^2+\dots$; this might prove to be useful. –  Guess who it is. Aug 19 '10 at 16:22

The first question that should be asked of any person presenting you with a large-ish matrix: "is the matrix dense or sparse?" In the latter case, one definitely does not need to allocate space for the zero entries, and should thus look into special techniques to storing them(which as I understand nowadays rely on a liberal dose of graph theory in the general case, though band matrices are still handled by storing their bands in an appropriate format).

Now, if even after that you have the perfect excuse for having a large dense matrix (which I still believe is quite unlikely), there is a way to invert and take the determinant of a large matrix via partitioning.

Say we have

$\textbf{A}=\begin{pmatrix}\textbf{E}&\textbf{F}\\ \textbf{G}&\textbf{H}\end{pmatrix}$

where $\textbf{E}$ and $\textbf{H}$ are square matrices with dimensions $m\times m$ and $n\times n$ respectively, and $\textbf{F}$ and $\textbf{G}$ are dimensioned appropriately (so the dimension of $\textbf{A}$ is $(m+n)\times(m+n)$). The inverse can then be computed as

$\textbf{A}^{-1}=\begin{pmatrix}\textbf{E}^{-1}+\left(\textbf{E}^{-1}\textbf{F}\right)(\textbf{H}-\textbf{G}\textbf{E}^{-1}\textbf{F})^{-1}\left(\textbf{G}\textbf{E}^{-1}\right)&-\left(\textbf{E}^{-1}\textbf{F}\right)(\textbf{H}-\textbf{G}\textbf{E}^{-1}\textbf{F})^{-1}\\-(\textbf{H}-\textbf{G}\textbf{E}^{-1}\textbf{F})^{-1}\left(\textbf{G}\textbf{E}^{-1}\right)&(\textbf{H}-\textbf{G}\textbf{E}^{-1}\textbf{F})^{-1}\end{pmatrix}$

where the parentheses emphasize common factors that you might profit from computing only once.

As for the determinant, it is given by

$\det\;\textbf{A}=\det\left(\textbf{H}-\textbf{G}\textbf{E}^{-1}\textbf{F}\right)\;\det\;\textbf{E}$

EDIT:

I'm not entirely sure what seemed to be unsatisfactory with this answer, so here's a bit more of exposition: as always, the "inverse" here is merely notation! One would most certainly first perform LU decomposition on $\textbf{E}$ and $\textbf{H}$ first. One would also partition the right-hand side $\textbf{b}$ accordingly:

$\textbf{b}=\begin{pmatrix}\textbf{c}\\ \textbf{d}\end{pmatrix}$

so $\textbf{c}$ is a length-m vector and $\textbf{d}$ is a length-n vector.

Formally multiplying the partitioned inverse with the partitioned right-hand side gives

$\begin{pmatrix}\textbf{E}^{-1}+\left(\textbf{E}^{-1}\textbf{F}\right)(\textbf{H}-\textbf{G}\textbf{E}^{-1}\textbf{F})^{-1}\left(\textbf{G}\textbf{E}^{-1}\right)&-\left(\textbf{E}^{-1}\textbf{F}\right)(\textbf{H}-\textbf{G}\textbf{E}^{-1}\textbf{F})^{-1}\\-(\textbf{H}-\textbf{G}\textbf{E}^{-1}\textbf{F})^{-1}\left(\textbf{G}\textbf{E}^{-1}\right)&(\textbf{H}-\textbf{G}\textbf{E}^{-1}\textbf{F})^{-1}\end{pmatrix}\cdot\begin{pmatrix}\textbf{c}\\ \textbf{d}\end{pmatrix}$

which when expanded and simplified is

$\begin{pmatrix}\textbf{E}^{-1}\textbf{c}+\left(\textbf{E}^{-1}\textbf{F}\right)(\textbf{H}-\textbf{G}\textbf{E}^{-1}\textbf{F})^{-1}\left(\textbf{G}\textbf{E}^{-1}\textbf{c}-\textbf{d}\right)\\-(\textbf{H}-\textbf{G}\textbf{E}^{-1}\textbf{F})^{-1}\left(\textbf{G}\textbf{E}^{-1}\textbf{c}-\textbf{d}\right)\end{pmatrix}$

At this point you should be able to figure out how you would use an available decomposition of $\textbf{E}$ or $\textbf{H}$, and which common subexpressions can be just computed once.

-
Hmm, there were new comments as I was typing this out; so the first formula would be the one applicable to you. It is up to you on how you will organize the computation of subexpressions in your code, just remember to partition your right hand side conformally with the matrix. –  Guess who it is. Aug 18 '10 at 23:08
Thank you! This is very helpful. Conceivably you could subdivide the matrix recursively then, and solve that way. I will leave this question open for a few days, in case there are any other solutions out there! –  bobobobo Aug 19 '10 at 15:17
bobobobo: "Recursively"... that would sound like setting yourself up for a administrative nightmare when you start writing the program. Two things: 1. you still haven't said why you have a dense matrix in the first place or where it came from. I would hope that it would have some sort of exploitable structure that you won't have to employ the baroque formula in my answer. 2. Again, it is a bad idea to maintain explicit inverses; store the matrices indicated as inverses in the formula above as an appropriate decomposition. –  Guess who it is. Aug 19 '10 at 15:39
The very dense matrix comes from the radiosity equation, which I discussed here: math.stackexchange.com/questions/2180/…. The matrix is usually quite dense! –  bobobobo Aug 19 '10 at 16:02
Ah, now I have seen where I obtained the formula from: check out "Computational Methods of Linear Algebra" by Faddeev and Faddeeva; the treatment is a bit dated but can still be useful. –  Guess who it is. Aug 20 '10 at 2:54

This is too long for a comment, so I'll throw in this choice piece by Forman Acton in his Numerical Methods That Work on the subject of dealing with large matrices:

Whenever a person eagerly inquires if my computer can solve a set of 300 equations in 300 unknowns, I must quickly suppress the temptation to retort, "Yes, but why bother?" There are, indeed, legitimate sets of equations that large. They arise from replacing a partial differential equation on a set of grid points, and the person who knows enough to tackle this type of problem also usually knows what kind of computer he needs. The odds are all too high that our inquiring friend is suffering from a quite different problem: he probably has collected a set of experimental data and is now attempting to fit a 300-parameter model to it - by Least Squares! The sooner this guy can be eased out of your office, the sooner you will be able to get back to useful work - but these chaps are persistent. They have fitted three-parameter models on desk machines with no serious difficulties and now the electronic computer permits them more grandiose visions. They leap from the known to the unknown with a terrifying innocence and the perennial self-confidence that every parameter is totally justified. It does no good to point out that several parameters are nearly certain to be competing to "explain" the same variations in the data and hence the equation system will be nearly indeterminate. It does no good to point out that all large least-squares matrices are striving mightily to be proper subsets of the Hilbert matrix-which is virtually indeterminate and uninvertible—and so even if all 300 parameters were beautifully independent, the fitting equations would still be violently unstable. All of this, I repeat, does no good—and you end up by getting angry and throwing the guy out of your office...

...The computer center's director must prevent the looting of valuable computer time by these would-be fitters of many parameters. The task is not a pleasant one, but the legitimate computer users have rights, too. The alternative commits everybody to a miserable two weeks of sloshing around in great quantities of "Results" that are manifestly impossible, with no visible way of finding the trouble. The trouble, of course, arises from looking for a good answer to a poorly posed problem, but a computer director seldom knows enough about the subject matter to win any of those arguments with the problem's proposer, and the impasse finally has to be broken by violence—which therefore might as well be used in the very beginning.

-
:) interesting, but not really an answer! –  bobobobo Aug 19 '10 at 15:59
It's supposed to be a comment, hence "community wiki". –  Guess who it is. Aug 19 '10 at 16:09

Essentially, there are two simple choices:

1. An iterative method that merely depends on repeatedly computing A*v and perhaps A'*v for a given vector 'v'. Such a computation can be done without having the entire matrix A in RAM

2. A direct method, for this the "out of core LU" might help.

In general, for both choices above, searching for external memory algorithms will be useful.

-
The matrix of interest is diagonally dominant, but unsymmetric and dense. An iterative method might work, but I think coming up with the matrix multiplication black box is going to be tough (though partitioning again might be useful here). –  Guess who it is. Sep 4 '10 at 10:08

If all you are interested in is solving $A x = B$, I would suggest looking at iterative and/or block-iterative methods. Noting your other question asking about positivity of solutions, I would suggest that you look at Applied and Computational Linear Algebra: A First Course by Charlie Byrne. The MART algorithm described therein is used for finding positive $x$ solutions to $A x = B$m, and addresses many similar problems from tomography and signal processing. If you like it get his 'Applied Iterative Methods'.

-
Dense, possibly unsymmetric and unstructured... I don't have high hopes for iterative approaches working well in his application. –  Guess who it is. Aug 19 '10 at 16:08
Density is likely a problem (it will be a problem with any method on matrices that large. The finiteness of floating point precision begins to hurt.) Iterative methods no longer need be symmetric, positive definite, or diagonally dominant, etc., to work. They do have the advantage of giving positive solutions, which it appears that he wants. –  deinst Aug 19 '10 at 16:25
Indeed, he would do well to have a look at the condition number of his matrix; if its logarithm is even just half of the number of digits of precision available he's short on luck. –  Guess who it is. Aug 19 '10 at 16:31
Aha: web.cs.wpi.edu/~matt/courses/cs563/talks/radiosity.html and particularly "it is diagonally dominant ... and the upper right of the matrix is computable from the lower left." Maybe your proposal would be a better use of computing power than mine! –  Guess who it is. Aug 19 '10 at 16:49