Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

We will briefly review connections between (i) the direct solvers which use multiresolution LU decomposition, (ii) multigrid and (iii) multiresolution reduction (homogenization) for self-adjoint, strictly elliptic operators. The multiresolution LU decomposition is, in essence, the Gaussian elimination interlaced with projections. The forward and backward substitution may then be interpreted as the ``direct' multigrid (a multigrid method without the W-cycles). The corrective W-cycles are not needed since on each scale we construct equations for the orthogonal projection of the {em true} solution. Once these equations are solved, there is no need to return to a coarser scale to correct the solution. Moreover, equations on coarser scales obtained in this manner are of interest by themselves, since they can be interpreted as reduced or ``homogenized' equations, leading to numerical multiresolution homogenization.

The key to our approach is the use of basis functions with vanishing moments since this property assures sparsity of matrices for a finite but arbitrary accuracy. The sparsity of matrices, in turn, leads to fast algorithms. The approach generalizes to multiple dimensions although additional steps have to be taken to improve the constants in complexity estimates of these algorithms.