MAx = Mb.
The sparse approximate inverse (SPAI) M
of a matrix A is a sparse matrix such that M ~ A^-1 and the number of
non-zeros in M is on the order of the number of non-zeros in A.
The existing implementation of SPAI
computes M in parallel, but has a major limitation. Each
processor gets an entire copy of A. If A gets too large, we may
run into memory constraints. So, it would be ideal if we could
distribute A across the processors in a way that avoids communication
among them. However, SPAI is an adaptive algorithm, and we cannot
accurately predict what parts of A will be required to compute each
column of M.
Our goal is to explore two major areas:
1) Effective distribution/decomposition of A.
This requires an analysis of the
mathematics behind SPAI. The implementation described in
[3] does not make any attempt to distribute A. The implementation
of [1] (by the authors of [1])) does distribute A, but does so without
regard to data content. This is better than [3], but [3] is
written in *P, while [1] is written in MPI. We aim to improve
upon the distribution of [1] (in MPI), but to do it in *P (building
from [3]).
2) Inter-processor communication in Matlab *P to enable access to
remote parts of A.
Currently, [3] uses
the 'mm' function in *P, which does not work for sparse matrices and
does not allow processors to access remote parts of A. We intend
to find a way to get access to the remotes parts of A.
There is a mechanism for using MPI communication calls within 'mm'
calls [4]. We are in the process of getting it to work on
machines at UCSB.