Keywords: Schur complement peconditioners, cyclic matrices, Sobolev norm representations, domain decomposition methods, fictitious domain methods, preconditioned conjugate gradient algorithm.

The Schur complement preconditioners play a determining role in the preconditioned conjugate gradient (PCG) algorithm [1,2] based fictitious domain and domain decomposition methods for elliptic problems [3,4,5,6,7,8].

We have developed several simple and efficient cyclic Schur complement preconditioning matrix constructions in the last years [9,10]. These constructions are based on the cyclic matrix representations of the Sobolev norm. However their application as Schur complement preconditioning matrix requires an approximate inverse matrix computation. It is a disadvantage of these constructions.

In this paper a new cyclic matrix representation of the norm is presented. This matrix has the following simple explicit form.

where

and is determined by the inequality.

Its application as Schur complement preconditioning matrix requires only matrix-vector multiplication. The computational cost of a matrix-vector multiplication by requires arithmetic operations for general , where is the number of unknowns.

We note that this preconditioning matrix has the same computational complexity as the widely used [7,8] and -matrix [11,12,13] type hierarchical preconditioning matrices, but its structure is much simpler. The preconditioning effect of to elliptic problems has been verified by numerical tests.

Acknowledgement

This work was partly supported by the Grants T043258 and T042826 of the Hungarian National Research Found.

1

A.A. Samarskij, E.S. Nikolajev, "Numerical Methods for Grid Equations", Bikhäuser, Basel, 1989.

2

C. Douglas, G. Haase, U. Langer, "A Tutorial on Elliptic PDE Solvers and Their Parallelisation", SIAM, 2003.

3

J.H. Bramble, J.E. Pasciak, A.H. Schatz, "The Construction of Preconditioners for Elliptic Problems by Substructuring I-IV." Math. of Comp. 47(175), 103-134, 49(184), 1-16, 51(184), 415-430, 53(187), 1-24, 1986-1989.

4

M. Dryja, "A Finite Element Capacitance Method For Elliptic Problems on Region Partitioned into Subregions", Numer. Math. 44, 153-168, 1984. doi:10.1007/BF01410102

5

O. Steinbach, W.L. Wendland, "The Construction of Some Efficient Preconditioners in Boundary Element Methods", Adv. Comput. Math. 9, 191-216, 1998. doi:10.1023/A:1018937506719

6

B.N. Koromskij, W.L. Wendland, "Spectrally Equivalent Preconditioners for Boundary Equations in Substructuring Techniques", East-West J. Numer. Math. 1, 1-27, 1993.

7

C.H. Tong, T.F. Chan, C.C.J. Kuo, "A Domain Decomposition Preconditioner Based on a Change to a Multilevel Nodal Basis", SIAM J. Sci. Stat. Comput. 12, 1486-1495, 1991. doi:10.1137/0912082

8

P. Oswald, "Multilevel Finite Element Approximation, Theory and Application", B.G. Teubner, Stuttgart, 1994.

9

B. Kiss, A. Krebsz, "Toeplitz Matrix Representation of the Norm", Periodica Math. Hungarica, 34(3), 201-210,1998. doi:10.1023/A:1004319404919

10

B. Kiss, A. Krebsz, "On the Schur Complement Preconditioners", Computers & Structures, 73 (1-5), 537-544, 1999. doi:10.1016/S0045-7949(98)00258-2

11

S. Börm, L. Grasedyck, W. Hackbusch, "Introduction to Hierarchical Matrices with Applications", Max-Planck-Institute, Leipzig, Preprint no. 18, 2002.

12

W. Hackbush, "A Sparse Matrix Arithmetic Based on H-matrices, Part I: Introduction to -matrices", Computing, 62, 89-108, 1999. doi:10.1007/s006070050015

13

W. Hackbush, B.N. Koromskij, "A Sparse Matrix Arithmetic Based on -matrices, Part II: Application to Multidimensional Problems", Computing, 64, 21-47, 2000.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)