Fast Parallel Algorithms for the Moore-Penrose Pseudo-Inverse

摘要

We employ the concept of an approximate pseudo-inverse (API) of a singular linear operator A to construct algorithms that yield the Moore-Penrose pseudo-inverse solution x sup + = A sup + y to the singular system Ax = y. Such an algorithm is a nonmatrix representation of the Moore-Penrose pseudo-inverse A sup + of A. We are particularly interested in fast algorithms (executable in O(n) operations) that are fully efficient on parallel computers. One result presented concerns the construction of APIs for consistent problems and is applied to the two-dimensional free-boundary spline interpolation problem. For this problem, the conjugate gradient algorithm, preconditioned with an API, proves to be very effective. The V-cycle multigrid algorithm FAPIN is shown to be an API if the smoother satisfies a certain condition and proves to be very effective for Poisson's problem on a two-torus. We have demonstrated our algorithms for n close to one million on the iPSC hypercube at Christian Michelsen Institute, Bergen. 15 refs., 1 tab. (ERA citation 12:010656)