ABSTRACT
This chapter provides construction of asymptotically optimal algorithms for a wide class of correct elliptic boundary value problems associated with bounded multidimensional domains. Construction of asymptotically optimal algorithms involves three basic subproblems: construction of asymptotically optimal Pragmatic General Multicast, construction of asymptotically optimal preconditioners leading to asymptotically optimal iterative methods, and application of coarse grid continuation. For multidimensional cases, these subproblems retain their fundamental significance, but yield additional theoretical and practical obstacles. The importance of this principle was emphasized probably for the first time in contrast to severed suggestions to use simplified operators with Dirichlet boundary conditions on the whole boundary. The chapter describes a simple but enlightening example given in, which deals with the one-dimensional case and difference operators. It considers the multigrid construction of asymptotically optimal preconditioners that were suggested in for grid approximations of basic boundary value problems in the theory of elasticity.
