×

Cyclic reduction and FACR methods for piecewise Hermite bicubic orthogonal spline collocation. (English) Zbl 0817.65093

The paper studies the solution of linear systems resulting from piecewise Hermite bicubic orthogonal spline collocation for separable partial differential equations on a rectangle. It is shown that cyclic reduction (CR) and Fourier analysis-cyclic reduction (FACR) methods can be applied. On an \(N\times N\) uniform grid these methods require \(O(N^ 2\log N)\) and \(O(N^ 2\log\log N)\) arithmetic operations, respectively.
Reviewer: G.Schmidt (Berlin)

MSC:

65N35 Spectral, collocation and related methods for boundary value problems involving PDEs
65F05 Direct numerical methods for linear systems and matrix inversion
35J25 Boundary value problems for second-order elliptic equations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J.C. Adams, Recent enhancements in MUDPACK, a multigrid software package for elliptic partial differential equations, Appl. Math. Comp. 43 (1991) 79–93. · Zbl 0727.65104 · doi:10.1016/0096-3003(91)90095-5
[2] K.R. Bennett, Parallel collocation methods for boundary value problems, Ph.D. Thesis, University of Kentucky, Lexington, KY (1991).
[3] B. Bialecki, An alternating direction implicit method for solving orthogonal spline collocation linear systems, Numer. Math. 59 (1991) 413–429. · Zbl 0738.65021 · doi:10.1007/BF01385789
[4] B. Bialecki, A fast domain decomposition Poisson solver on a rectangle for Hermite bicubic orthogonal spline collocation, SIAM J. Numer. Anal. 30 (1993) 425–434. · Zbl 0774.65080 · doi:10.1137/0730020
[5] B. Bialecki, Preconditioned Richardson and minimal residual iterative methods for piecewise Hermite bicubic orthogonal spline collocation equations, SIAM J. Sci. Comp. 15 (1994) 668–680. · Zbl 0810.65107 · doi:10.1137/0915043
[6] B. Bialecki, G. Fairweather and K.R. Bennett, Fast direct solvers for piecewise Hermite bicubic orthogonal spline collocation equations, SIAM J. Numer. Anal. 29 (1992) 156–173. · Zbl 0752.65076 · doi:10.1137/0729010
[7] B. Bialecki, G. Fairweather and K.R. Remington, Fourier methods for piecewise Hermite bicubic orthogonal spline collocation, East-West J. Numer. Math. 2 (1994) 1–20. · Zbl 0805.65107
[8] R.F. Boisvert, Algorithm 651, Algorithm HFFT-Higher-order fast-direct solution of the Helmholtz equation, ACM Trans. Math. Software 13 (1987) 235–249. · doi:10.1145/29380.214342
[9] C. De Boor,A Practical Guide to Splines, Applied Mathematical Sciences 27 (Springer, New York, 1978). · Zbl 0406.41003
[10] B.L. Buzbee, G.H. Golub and C.W. Nielson, On direct methods for solving Poisson’s equations, SIAM J. Number. Anal. 7 (1970) 627–656. · Zbl 0217.52902 · doi:10.1137/0707049
[11] O. Buneman, A compact non-iterative Poisson solver, Rep. 294, Stanford University Institute for Plasma Research, Stanford, CA (1969). · Zbl 0219.68055
[12] J.C. Diaz, G. Fairweather and P. Keast, FORTRAN packages for solving certain almost block diagonal linear systems by modified alternate row and column elimination, ACM Trans. Math. Software 9 (1983) 358–375. · Zbl 0516.65013 · doi:10.1145/356044.356053
[13] J.C. Diaz, G. Fairweather and P. Keast, Algorithm 603 COLROW and ARCECO: FORTRAN packages for solving certain almost block diagonal linear systems by modified alternate row and column elimination, ACM Trans. Math. Software 9 (1983) 376–380. · Zbl 0516.65013 · doi:10.1145/356044.356054
[14] J. Douglas, Jr. and T. Dupont,Collocation Methods for Parabolic Equations in a Single Space Variable, Lecture Notes in Mathematics 385 (Springer, New York, 1974). · Zbl 0279.65097
[15] G. Fairweather, A note on the efficient implementation of certain Padé methods for linear parabolic problems, BIT 18 (1978) 106–109. · Zbl 0384.65036 · doi:10.1007/BF01947749
[16] G. Fairweather,Finite Element Galerkin Methods for Differential Equations, Lecture Notes in Pure and Applied Mathematics, Vol. 34 (Marcel Dekker, New York, 1978). · Zbl 0372.65044
[17] E. Gallopoulos and Y. Saad, A parallel block cyclic reduction algorithm for the fast solution of elliptic equations, Parallel Comp. 10 (1989) 143–159. · Zbl 0676.65098 · doi:10.1016/0167-8191(89)90014-8
[18] P. Percell and M.F. Wheeler, AC 1 finite element collocation method for elliptic equations, SIAM J. Numer. Anal. 17 (1980) 605–622. · Zbl 0532.65076 · doi:10.1137/0717050
[19] L. Reichel, The ordering of tridiagonal matrices in the cyclic reduction method for Poisson’s equation, Numer. Math. 56 (1989) 215–227. · Zbl 0686.65067 · doi:10.1007/BF01409785
[20] A.A. Samarskii and E.S. Nikolaev,Numerical Methods for Grid Equations, Vol. 1:Direct Methods (Birkhäuser, Basel, 1989).
[21] P.N. Swarztrauber, A direct method for the discrete solution of separable elliptic equations, SIAM J. Numer. Anal. 11 (1974) 1136–1150. · Zbl 0292.65054 · doi:10.1137/0711086
[22] P.N. Swarztrauber, The methods of cyclic reduction, Fourier analysis and the FACR algorithm for the discrete solution of Poisson’s equation on a rectangle, SIAM Rev. 19 (1977) 490–501. · Zbl 0358.65088 · doi:10.1137/1019071
[23] P.N. Swarztrauber, Fast Poisson solvers, in:Studies in Numerical Analysis, ed. G.H. Golub, MAA Studies in Mathematics, Vol. 24 (Mathematical Association of America, 1984) pp. 319–370. · Zbl 0597.65084
[24] P.N. Swarztrauber and R.A. Sweet, Algorithm 541, efficient Fortran subprograms for the solution of separable elliptic partial differential equations, ACM Trans. Math. Software 5 (1979) 352–364. · Zbl 0419.35043 · doi:10.1145/355841.355850
[25] R.A. Sweet, A cyclic reduction algorithm for solving block tridiagonal systems of arbitrary dimension, SIAM J. Numer. Anal. 14 (1977) 706–720. · Zbl 0366.65015 · doi:10.1137/0714048
[26] C. Temperton, Direct methods for the solution of the discrete Poisson equation: some comparisons, J. Comp. Phys. 31 (1979) 1–20. · Zbl 0397.65079 · doi:10.1016/0021-9991(79)90059-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.