Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Civil-Comp Proceedings
ISSN 1759-3433
CCP: 80
PROCEEDINGS OF THE FOURTH INTERNATIONAL CONFERENCE ON ENGINEERING COMPUTATIONAL TECHNOLOGY
Edited by: B.H.V. Topping and C.A. Mota Soares
Paper 57

On the Cyclic Preconditioning Matrix Constructions

B. Kiss

Department of Mathematics, Széchenyi István University, Gyor, Hungary

Full Bibliographic Reference for this paper
B. Kiss, "On the Cyclic Preconditioning Matrix Constructions", in B.H.V. Topping, C.A. Mota Soares, (Editors), "Proceedings of the Fourth International Conference on Engineering Computational Technology", Civil-Comp Press, Stirlingshire, UK, Paper 57, 2004. doi:10.4203/ccp.80.57
Keywords: Schur complement peconditioners, cyclic matrices, Sobolev norm representations, domain decomposition methods, fictitious domain methods, preconditioned conjugate gradient algorithm.

Summary
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.

(16)
  (17)

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.

References
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)