MULTILEVEL SUBSTRUCTURING PRECONDITIONING
                OF NONCONFORMING FINITE ELEMENT APPROXIMATIONS
                      OF SECOND ORDER ELLIPTIC PROBLEMS

                              SERGUEI MALIASSOV
                   Institute for Scientific Computation and
                          Department of Mathematics,
                            Texas A&M University,
                         326 Teague Research Center, 
                       College Station, TX 77843-3404.
                        E-mail:  malyasov@isc.tamu.edu

Abstract.  A new approach to constructing algebraic m ultigrid preconditioners
for nonconforming finite element approximations of diffusion op erators on
tetrahedral grids is presented.

First, using an idea of partitioning (decomposing) a parallelepiped grid into
tetrahedral substructures a two-level preconditioner is constructed and the
condition number of the preconditioned matrix is estimated.  Then, it is shown
that on the coarser level the system is reduced to 7-point-scheme problem with
one unknown per parallelepiped.  For such a system standard multigrid domain
decomposition method is used.

Explicit estimates of condition numbers are established for the constructed
two-level and multigrid methods.  It is shown that condition numbers do not
depend on jump of the coefficients of the diffusion operators.

The preconditioner constructed may be considered to belong to the class of
optimal preconditioners since it is spectrally equivalent to the original
stiffness matrix and its arithmetic cost is proportional to the dimension of
the problem with the proportionality factor independent of the grid step size.
Finally , estimates of arithmetic complexity of the method suggested and
results of numerical experiments are presented to illustrate the theory being
considered.

Key words.  Domain decomposition methods, multilevel substructuring
preconditioners, superelements, iterative methods.