Abstract
We provide an overview of matrix decomposition algorithms (MDAs) for the solution of systems of linear equations arising when various discretization techniques are applied in the numerical solution of certain separable elliptic boundary value problems in the unit square. An MDA is a direct method which reduces the algebraic problem to one of solving a set of independent one-dimensional problems which are generally banded, block tridiagonal, or almost block diagonal. Often, fast Fourier transforms (FFTs) can be employed in an MDA with a resulting computational cost of O(N 2 logN) on an N × N uniform partition of the unit square. To formulate MDAs, we require knowledge of the eigenvalues and eigenvectors of matrices arising in corresponding two–point boundary value problems in one space dimension. In many important cases, these eigensystems are known explicitly, while in others, they must be computed. The first MDAs were formulated almost fifty years ago, for finite difference methods. Herein, we discuss more recent developments in the formulation and application of MDAs in spline collocation, finite element Galerkin and spectral methods, and the method of fundamental solutions. For ease of exposition, we focus primarily on the Dirichlet problem for Poisson’s equation in the unit square, sketch extensions to other boundary conditions and to more involved elliptic problems, including the biharmonic Dirichlet problem, and report extensions to three dimensional problems in a cube. MDAs have also been used extensively as preconditioners in iterative methods for solving linear systems arising from discretizations of non-separable boundary value problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abakumov, A.A., Yeremin, Y.A., Kuznetsov, Y.A.: Efficient fast direct method of solving Poisson’s equation on a parallelepiped and its implementation in an array processor. Sov. J. Numer. Anal. Math. Model. 3, 1–20 (1988)
Abushama, A.A., Bialecki, B.: Modified nodal cubic spline collocation for biharmonic equations. Numer. Algorithms 43, 331–353 (2006)
Abushama, A.A., Bialecki, B.: Modified nodal cubic spline collocation for Poisson’s equation. SIAM J. Numer. Anal. 46, 397–418 (2008)
Amodio, P., Cash, J.R., Roussos, G., Wright, R.W., Fairweather, G., Gladwell, I., Kraut, G.L., Paprzycki, M.: Almost block diagonal linear systems: sequential and parallel solution techniques, and applications. Numer. Linear Algebra Appl. 7, 275–317 (2000)
Anastassiu, H.T., Lymperopoulos, D.G., Kaklamani, D.I.: Accuracy analysis and optimization of the method of auxiliary sources (MAS) for scattering by a circular cylinder. IEEE Trans. Antennas Propag. 52, 1541–1547 (2004)
Anastassiu, H.T., Volakis, J.L., Filipovic, D.S.: Integral equation modeling of cylindrically periodic scatterers in the interior of a cylindrical waveguide. IEEE Trans. Microwave Theor. Tech. 46, 1713–1720 (1998)
Archer, D.: Some collocation methods for differential equations. Ph.D. thesis, Rice University, Houston, Texas (1973)
Archer, D.: An O(h 4) cubic spline collocation method for quasilinear parabolic equations. SIAM J. Numer. Anal. 14, 620–637 (1977)
Auteri, F., Parolini, N., Quartapelle, L.: Essential imposition of Neumann condition in Galerkin-Legendre elliptic solvers. J. Comput. Phys. 185, 427–444 (2003)
Auteri, F., Quartapelle, L.: Galerkin spectral method for the vorticity and stream function equations. J. Comput. Phys. 149, 306–332 (1999)
Auteri, F., Quartapelle, L.: Galerkin–Legendre spectral method for the 3D Helmholtz equation. J. Comput. Phys. 161, 454–483 (2000)
Auteri, F., Quartapelle, L.: Spectral elliptic solvers in a finite cylinder. Commun. Comput. Phys. 5, 426–441 (2009)
Auteri, F., Quartapelle, L., Vigevano, L.: Accurate ω − ψ spectral solution of the singular driven cavity problem. J. Comput. Phys. 180, 597–615 (2002)
Azaiez, M., Shen, J., Xu, C., Zhuang, Q.: A Laguerre-Legendre spectral method for the Stokes problem in a semi-infinite channel. SIAM J. Numer. Anal. 47, 271–292 (2009)
Bade, F., Haldenwang, P.: High order scheme for thermally driven flows in an open channel. Comput. Fluids 27, 273–290 (1999)
Banegas, A.: Fast Poisson solvers for problems with sparsity. Math. Comput. 32, 441–446 (1978)
Bank, R.E.: Efficient algorithms for solving tensor product finite element equations. Numer. Math. 31, 49–61 (1978)
Bao, G., Sun, W.: A fast algorithm for the electromagnetic scattering from a large cavity. SIAM J. Sci. Comput. 27, 553–574 (2005)
Ben–Artzi, M., Croisille, J.-P., Fishelov, D.: A fast direct solver for the biharmonic problem in a rectangular grid. SIAM J. Sci. Comput. 31, 303–333 (2008)
Bennett, K.R.: Parallel collocation methods for boundary value problems. Ph.D. thesis, University of Kentucky, Lexington, Kentucky (1991)
Bialecki, B.: A fast domain decomposition Poisson solver on a rectangle for Hermite bicubic orthogonal spline collocation. SIAM J. Numer. Anal. 30, 425–434 (1993)
Bialecki, B.: A fast solver for the orthogonal spline collocation solution of the biharmonic Dirichlet problem on rectangles. J. Comput. Phys. 191, 601–621 (2003)
Bialecki, B.: Piecewise Hermite bicubic orthogonal spline collocation for Poisson’s equation on a disk (preprint)
Bialecki, B., Cai, X.-C., Dryja, M., Fairweather, G.: An additive Schwarz algorithm for piecewise Hermite bicubic orthogonal spline collocation. In: Domain Decomposition Methods in Science and Engineering (Como 1992). Contemp. Math., vol. 157, pp. 237–244. Amer. Math. Soc., Providence, Rhode Island (1994)
Bialecki, B., Dillery, D.S.: Fourier analysis of Schwarz alternating methods for piecewise Hermite bicubic orthogonal spline collocation. BIT 33, 634–646 (1993)
Bialecki, B., Dryja, M.: A nonoverlapping domain decomposition method for orthogonal spline collocation problems. SIAM J. Numer. Anal. 41, 1709–1728 (2003)
Bialecki, B., Fairweather, G.: Matrix decomposition algorithms for separable elliptic boundary value problems in two dimensions. J. Comput. Appl. Math. 46, 369–386 (1993)
Bialecki, B., Fairweather, G.: Matrix decomposition algorithms in orthogonal spline collocation for separable elliptic boundary value problems. SIAM J. Sci. Comput. 16, 330–347 (1995)
Bialecki, B., Fairweather, G.: Orthogonal spline collocation methods for partial differential equations. J. Comput. Appl. Math. 128, 55–82 (2001)
Bialecki, B., Fairweather, G., Bennett, K.R.: Fast direct solvers for piecewise Hermite bicubic orthogonal spline collocation equations. SIAM J. Numer. Anal. 29, 156–173 (1992)
Bialecki, B., Fairweather, G., Karageorghis, A.: Matrix decomposition algorithms for modified spline collocation for Helmholtz problems. SIAM J. Sci. Comput. 24, 1733–1753 (2003)
Bialecki, B., Fairweather, G., Karageorghis, A.: Optimal superconvergent one step nodal cubic spline collocation methods. SIAM J. Sci. Comput. 27, 575–598 (2005)
Bialecki, B., Fairweather, G., Karageorghis, A., Nguyen, Q.N.: On the formulation and implementation of optimal superconvergent one step quadratic spline collocation methods for elliptic problems. Technical Report TR/18/2007, Department of Mathematics and Statistics, University of Cyprus (2007)
Bialecki, B., Fairweather, G., Karageorghis, A., Nguyen, Q.N.: Optimal superconvergent one step quadratic spline collocation methods for Helmholtz equations. In: Jorgensen, P., Shen, X., Shu, C.-W., Yan, N. (eds.) Recent Advances in Computational Science, pp. 156–174. World Scientific, Singapore (2008)
Bialecki, B., Fairweather, G., Karageorghis, A., Nguyen, Q.N.: Optimal superconvergent one step quadratic spline collocation methods. BIT 48, 449–472 (2008)
Bialecki, B., Fairweather, G., Knudson, D.B., Lipman, D.A., Nguyen, Q.N., Sun, W., Weinberg, G.M.: Matrix decomposition algorithms for the finite element Galerkin method with piecewise Hermite cubics. Numer. Algorithms 52, 1–23 (2009)
Bialecki, B., Fairweather, G., Remington, K.A.: Fourier methods for piecewise Hermite bicubic orthogonal spline collocation. East-West J. Numer. Math. 2, 1–20 (1994)
Bialecki, B., Karageorghis, A.: A Legendre spectral collocation method for the biharmonic Dirichlet problem. M2AN Math. Model. Numer. Anal. 34, 637–662 (2000)
Bialecki, B., Karageorghis, A.: A Legendre spectral Galerkin method for the biharmonic Dirichlet problem. SIAM J. Sci. Comput. 22, 1549–1569 (2000)
Bialecki, B., Karageorghis, A.: Legendre Gauss spectral collocation for the Helmholtz equation on a rectangle. Numer. Algorithms 36, 203–227 (2004)
Bialecki, B., Karageorghis, A.: A nonoverlapping domain decomposition method for Legendre spectral collocation problems. J. Sci. Comput. 32, 373–409 (2007)
Bialecki, B., Karageorghis, A.: Spectral Chebyshev-Fourier collocation for the Helmholtz and variable coefficient equations in a disk. J. Comput. Phys. 227, 8588–8603 (2008)
Bialecki, B., Karageorghis, A.: Spectral Chebyshev collocation for Poisson and biharmonic equations (submitted)
Bialecki, B., Remington, K.A.: Fourier matrix decomposition methods for the least squares solution of singular Neumann and periodic Hermite bicubic collocation problems. SIAM J. Sci. Comput. 16, 431–451 (1995)
Bialecki, B., Wang, Z.: Modified nodal cubic spline collocation for elliptic equations (submitted)
Bickley, W.S.: Finite difference formulae for the square lattice. Q. J. Mech. Appl. Math. 1, 35–42 (1948)
Bickley, W.S., McNamee, J.: Matrix and other direct methods for the solution of systems of linear difference equations. Philos. Trans. R. Soc. Lond., Ser. A. 252, 69–131 (1960)
Bjøntegaard, T., Maday, Y., Rønquist, E.M.: Fast tensor-product solvers: partially deformed three-dimensional domains. J. Sci. Comput. 39, 28–48 (2009)
Bjørstad, P.E.: Fast numerical solution of the biharmonic Dirichlet problem on rectangles. SIAM J. Numer. Anal. 20, 59–71 (1983)
Bjørstad, P.E., Tjøstheim, B.P.: Efficient algorithms for solving a fourth-order equation with the spectral-Galerkin method. SIAM J. Sci. Comput. 18, 621–632 (1997)
Bjørstad, P.E., Tjøstheim, B.P.: High precision solutions of two fourth order eigenvalue problems. Computing 63, 97–107 (1999)
Boisvert, R.F.: Families of high order accurate discretizations of some elliptic problems. SIAM J. Sci. Statist. Comput. 2, 268–284 (1981)
Boisvert, R.F.: High order compact difference formulas for elliptic problems with mixed boundary conditions. In: Vichnevetsky, R., Stepleman, R.S. (eds.) Advances in Computer Methods for Partial Differential Equations IV, pp. 193–199. IMACS, Rutgers University, New Brunswick, New Jersey (1981)
Boisvert, R.F.: A fourth-order accurate fast direct method for the Helmholtz equation. In: Birkhoff, G., Schoenstadt, A. (eds.) Elliptic Problem Solvers II, pp. 35–44. Academic, Orlando, Florida (1984)
Boisvert, R.F.: A fourth-order-accurate Fourier method for the Helmholtz equation in three dimensions. ACM Trans. Math. Softw. 13, 221–234 (1987)
Boisvert, R.F.: Algorithm 651: HFFT—high-order fast-direct solution of the Helmholtz equation. ACM Trans. Math. Softw. 13, 235–249 (1987)
de Boor, C.: The method of projections as applied to the numerical solution of two point boundary value problems using cubic splines. Ph.D. thesis, University of Michigan, Ann Arbor, Michigan (1966)
Bottcher, C., Strayer, M.R.: The basis spline method and associated techniques. In: Bottcher, C., Strayer, M.R., McGrory, J.B. (eds.) Computational Atomic and Nuclear Physics, pp. 217–240. World Scientific, Singapore (1990)
Bottcher, C., Strayer, M.R.: Spline methods for conservation equations. In: Lee, D., Robinson, A.R., Vichnevetsky, R. (eds.) Computational Acoustics, vol. 2, pp. 317–338. Elsevier, Amsterdam (1993)
Boyd, J.P.: Chebyshev and Fourier Spectral Methods. 2nd edn. Dover, New York (2001)
Buzbee, B.L., Golub, G.H., Nielson, C.W.: On direct methods for solving Poisson’s equation. SIAM J. Numer. Anal. 7, 627–656 (1970)
Canuto, C., Hussaini, M.Y., Quarteroni, A., Zang, T.A.: Spectral Methods. Fundamentals in Single Domains. Springer, New York (2006)
Chan, T.F., Resasco, D.C.: A domain–decomposed fast Poisson solver on a rectangle. SIAM J. Sci. Statist. Comput. 8, 14–26 (1987)
Chan, T.F., Resasco, D.C.: Errata: a domain–decomposed fast Poisson solver on a rectangle. SIAM J. Sci. Statist. Comput. 8, 457 (1987)
Chen, H.B., Nandakumar, K., Finlay, W.H., Ku, H.C.: Three-dimensional viscous flow through a rotating channel: a pseudospectral matrix method approach. Int. J. Numer. Methods Fluids 23, 379–396 (1996)
Chen, H., Su, Y., Shizgal, B.D.: A direct spectral collocation Poisson solver in polar and cylindrical coordinates. J. Comput. Phys. 160, 453–469 (2000)
Chen, Y., Yi, N., Liu, W.: A Legendre-Galerkin spectral method for optimal control problems governed by elliptic equations. SIAM J. Numer. Anal. 46, 2254–2275 (2008)
Christara, C.C.: Quadratic spline collocation methods for elliptic partial differential equations. BIT 34, 33–61 (1994)
Christara, C.C., Ng, K.S.: Fast Fourier transform solvers and preconditioners for quadratic spline collocation. BIT 42, 702–739 (2002)
Constas, A.: Fast Fourier transform solvers for quadratic spline collocation. M.Sc. thesis, Department of Computer Science, University of Toronto (1996)
Daniel, J.W., Swartz, B.K.: Extrapolated collocation for two-point boundary value problems using cubic splines. J. Inst. Math. Appl. 16, 161–174 (1975)
Doha, E.H.: Efficient Jacobi Galerkin methods for second- and fourth-order elliptic problems. J. Egypt. Math. Soc. 16, 161–213 (2008)
Doha, E.H., Abd-Elhameed, W.M.: Efficient spectral-Galerkin algorithms for direct solution of second-order equations using ultraspherical polynomials. SIAM J. Sci. Comput. 24, 548–571 (2002)
Doha, E.H., Abd-Elhameed, W.M., Bhrawy, A.H.: Efficient spectral ultraspherical-Galerkin algorithms for the direct solution of 2nth-order linear differential equations. Appl. Math. Model. 33, 1982–1996 (2009)
Doha, E.H., Bhrawy, A.H.: Efficient spectral-Galerkin algorithms for direct solution of the integrated forms of second-order equations using ultraspherical polynomials. Numer. Algorithms 42, 137–164 (2006)
Doha, E.H., Bhrawy, A.H.: Efficient spectral-Galerkin algorithms for direct solution of second-order differential equations using Jacobi polynomials. ANZIAM J. 48, 361–386 (2007)
Doha, E.H., Bhrawy, A.H.: Efficient spectral-Galerkin algorithms for direct solution of fourth-order differential equations using Jacobi polynomials. Appl. Numer. Math. 58, 1224–1244 (2008)
Doha, E.H., Bhrawy, A.H., Abd-Elhameed, W.M.: Jacobi spectral Galerkin method for elliptic Neumann problems. Numer. Algorithms 50, 67–91 (2009)
Dorr, F.W. (1970). The direct solution of the discrete Poisson equation on a rectangle. SIAM Rev. 12, 248–263 (1970)
Dui, K., Fairweather, G., Nguyen, Q.N., Sun, W.: Matrix decomposition algorithms for the C 0–quadratic finite element Galerkin method. BIT 49, 509–526 (2009)
Dyksen, W.R.: Tensor product generalized ADI methods for separable elliptic problems. SIAM J. Numer. Anal. 24, 59–76 (1987)
Egerváry, E.: Űber eine Methode zur numerischen Lősung der Poissonschen Differenzengleichung für beliebige Gebeite. Acta. Math. Acad. Sci. Hungar. 11, 341–361 (1960)
Ehrenstein, U., Peyret, R.: A Chebyshev collocation method for the Navier-Stokes equations with application to double-diffusive convection. Int. J. Numer. Methods Fluids 9, 427–452 (1989)
Elbardary, E.M.E.: Efficient Chebyshev-Petrov-Galerkin method for solving second order equations. J. Sci. Comput. 34, 113–126 (2008)
Elman, H.C., O’Leary, D.P.: Efficient iterative solution of the three–dimensional Helmholtz equation. J. Comput. Phys. 142, 163–181 (1998)
Ernst, O., Golub, G.H.: A domain decomposition approach to solving the Helmholtz equation with a radiation boundary condition. In: Domain Decomposition Methods in Science and Engineering (Como, 1992). Contemp. Math., vol. 157, pp. 177–192. Amer. Math. Soc., Providence, Rhode Island (1994)
Fairweather, G.: Finite Element Galerkin Methods for Differential Equations. Lecture Notes in Pure and Applied Mathematics, vol. 34. Marcel Dekker, New York (1978)
Fairweather, G., Bennett, K.R., Bialecki, B.: Parallel matrix decomposition algorithms for separable elliptic boundary value problems. In: Noye, B.J., Benjamin, B.R., Colgan, L.H. (eds.) Computational Techniques and Applications: CTAC-91, Proceedings of the 1991 International Conference on Computational Techniques and Applications, Adelaide, South Australia, July 1991, pp. 63–74. Computational Mathematics Group, Australian Mathematical Society (1992)
Fairweather, G., Gladwell, I.: Algorithms for almost block diagonal linear systems. SIAM Rev. 46, 49–58 (2004)
Fairweather, G., Karageorghis, A.: The method of fundamental solutions for elliptic boundary value problems. Adv. Comput. Math. 9, 69–95 (1998)
Fairweather, G., Karageorghis, A., Maack, J.: Compact optimal quadratic spline collocation methods for Poisson and Helmholtz problems: formulation and numerical verification. Technical Report TR/03/2010, Department of Mathematics and Statistics, University of Cyprus (2010)
Fairweather, G., Karageorghis, A., Smyrlis, Y.-S.: A matrix decomposition MFS algorithm for axisymmetric biharmonic problems. Adv. Comput. Math. 23, 55–71 (2005)
Fyfe, D.J.: The use of cubic splines in the solution of two-point boundary value problems. Comput. J. 13, 188–192 (1969)
Garba, A.: A mixed spectral/wavelet method for the solution of the Stokes problem. J. Comput. Phys. 145, 297–315 (1998)
Golub, G.H., Huang, L.C., Simon, H., Tang, W.-P.: A fast Poisson solver for the finite difference solution of the incompressible Navier Stokes equations. SIAM J. Sci. Comput. 19, 1606–1624 (1998)
Gottlieb, D., Lustman, L.: The spectrum of the Chebyshev collocation operator for the heat equation. SIAM J. Numer. Anal. 20, 909–921 (1983)
Guessous, L.: A pseudo-spectral numerical scheme for the simulation of steady and oscillating wall-bounded flows. Numer. Heat Transf., B 45, 135–157 (2004)
Gustafsson, B., Hemmingsson–Frändén, L.: A fast domain decomposition high order Poisson solver. J. Sci. Comput. 14, 223–243 (1999)
Haidvogel, D.B., Zang, T.: The accurate solution of Poisson’s equation by expansion in Chebyshev polynomials. J. Comput. Phys. 30, 167–180 (1979)
Haldenwang, P., Labrosse, G., Abboudi, S., Deville, M.: Chebyshev 3–D spectral and 2–D pseudospectral solvers for the Helmholtz equation. J. Comput. Phys. 55, 115–128 (1984)
Heikkola, E., Kuznetsov, Y.A., Lipnikov, K.N.: Fictitious domain methods for the numerical solution of three–dimensional acoustic scattering problems. J. Comput. Acoust. 7, 161–183 (1999)
Heikkola, E., Rossi, T., Toivanen, J.: Fast direct solution of the Helmholtz equation with a perfectly matched or an absorbing boundary condition. Int. J. Numer. Methods Eng. 57, 2007–2025 (2003)
Heinrichs, W.: Improved condition number for spectral methods. Math. Comput. 53, 103–119 (1989)
Heinrichs, W.: Spectral methods with sparse matrices. Numer. Math. 56, 25–41 (1989)
Heinrichs, W.: Algebraic spectral multigrid methods. Comput. Methods Appl. Mech. Eng. 80, 281–286 (1990)
Heinrichs, W.: A stabilized treatment of the biharmonic operator with spectral methods. SIAM J. Sci. Comput. 12, 1162–1172 (1991)
Hendrickx, J., Van Barel, M.: A Kronecker product variant of the FACR method for solving the generalized Poisson equation. J. Comput. Appl. Math. 140, 369–380 (2002)
Hendrickx, J., Vandebril, R., Van Barel, M.: A fast direct method for solving the two–dimensional Helmholtz equation, with Robbins boundary conditions. In: Fast Algorithms for Structured Matrices: Theory and Applications. Contemp. Math., vol. 323, pp. 187–204. Amer. Math. Soc., Providence, Rhode Island (2003)
Hill, R.W., Ball, K.S.: Direct numerical simulations of turbulent forced convection between counter-rotating disks. Int. J. Heat Fluid Flow 20, 208–221 (1999)
Hill, R.W., Ball, K.S.: Parallel implementation of a Fourier-Chebyshev collocation method for incompressible fluid flow and heat transfer. Numer. Heat Transf., B 36, 309–329 (1999)
Ho, A.C., Ng, M.K.: Iterative methods for Robbins problem. Appl. Math. Comput. 165, 103–125 (2005)
Hockney, R.W.: A fast direct solution of Poisson’s equation using Fourier analysis. J. Assoc. Comput. Mach. 12, 95–113 (1965)
Houstis, E.N., Christara, C.C., Rice, J.R.: Quadratic-spline collocation methods for two-point boundary value problems. Int. J. Numer. Methods Eng. 26, 935–952 (1988)
Houstis, E.N., Vavalis, E.A., Rice, J.R.: Convergence of O(h 4) cubic spline collocation methods for elliptic partial differential equations. SIAM J. Numer. Anal. 25, 54–74 (1988)
Hu, Y., Ling, X.: Preconditioners for elliptic problems via non–uniform meshes. Appl. Math. Comput. 181, 1182–1198 (2006)
Hyman, M.A.: Non iterative numerical solution of boundary value problems. Appl. Sci. Res., B 2, 325–351 (1951)
Ierley, G.R.: A class of sparse spectral operators for inversion of powers of the Laplacian in N dimensions. J. Sci. Comput. 12, 57–73 (1997)
Ito, K., Qiao, Z., Toivanen, J.: A domain decomposition solver for acoustic scattering by elastic objects in layered media. J. Comput. Phys. 227, 8685–8698 (2008)
Julien, K., Watson, M.: Efficient multi-dimensional solution of PDEs using Chebyshev spectral methods. J. Comput. Phys. 228, 1480–1503 (2009)
Jun, S., Kang, S., Kwon, Y.: A direct solver for the Legendre tau approximation for the two-dimensional Poisson problem. J. Appl. Math. Comput. 23, 25–42 (2007)
Kadalbajoo, M.K., Bharadwaj, K.K.: Fast elliptic solvers—an overview. Appl. Math. Comput. 14, 331–355 (1984)
Karageorghis, A.: Efficient MFS algorithms in regular polygonal domains. Numer. Algorithms 50, 215–240 (2009)
Karageorghis, A.: Efficient Kansa-type MFS algorithm for elliptic problems. Numer. Algorithms (to appear). doi:10.1007/s11075-009-9334-8
Karageorghis, A., Chen, C.S., Smyrlis, Y.-S.: Matrix decomposition RBF algorithm for solving 3d elliptic problems. Eng. Anal. Bound. Elem. 33, 1368–1373 (2009)
Karageorghis, A., Kyza, I.: Efficient algorithms for approximating particular solutions of elliptic equations using Chebyshev polynomials. Commun. Comput. Phys. 2, 501–521 (2007)
Karageorghis, A., Smyrlis, Y.-S.: Matrix decomposition MFS algorithms for elasticity and thermo-elasticity problems in axisymmetric domains. J. Comput. Appl. Math. 206, 774–795 (2007)
Karageorghis, A., Smyrlis, Y.-S.: Matrix decomposition algorithms related to the MFS for axisymmetric problems. In: Manolis, G.D., Polyzos, D. (eds.) Recent Advances in Boundary Element Methods, pp. 223–237. Springer, New York (2009)
Kaufman, L., Warner, D.: High–order, fast–direct methods for separable elliptic equations. SIAM J. Numer. Anal. 21, 674–694 (1984)
Kaufman, L., Warner, D.: Algorithm 685: a program for solving separable elliptic equations. ACM Trans. Math. Softw. 16, 325–351 (1990)
Kegley, D.R., Jr., Oberacker, V.E., Strayer, M.R., Umar, A.S., Wells, J.C.: Basis spline collocation method for solving the Schrödinger equation in axillary symmetric systems. J. Comput. Phys. 128, 197–208 (1996)
Knudson, D.B.: A piecewise Hermite bicubic finite element Galerkin method for the biharmonic Dirichlet problem. Ph.D. thesis, Colorado School of Mines, Golden, Colorado (1997)
Kurz, S., Rain, O., Rjasanow, S.: Application of the adaptive cross approximation technique for the coupled BE–FE solution of symmetric electromagnetic problems. Comput. Mech. 32, 423–429 (2003)
Kuznetsov, Yu.A.: Numerical methods in subspaces. In: Marchuk, G.I. (ed.) Vychislitel’nye Processy i Sistemy II, pp. 265–350. Naukam Moscow (1985) (in Russian)
Kuznetsov, Yu.A., Matsokin, A.M.: On partial solution of systems of linear algebraic equations. Sov. J. Numer. Anal. Math. Model. 4, 453–468 (1989)
Kuznetsov, Yu.A., Rossi, T.: Fast direct method for solving algebraic systems with separable symmetric band matrices. East-West J. Numer. Math. 4, 53–68 (1996)
Kwan, Y.-Y.: Efficient spectral-Galerkin methods for polar and cylindrical geometries. Appl. Numer. Math. 59, 170–186 (2009)
Kwan, Y.-Y., Shen, J.: An efficient direct parallel spectral-element solver for separable elliptic problems. J. Comput. Phys. 225, 1721–1735 (2007)
Lai, M.-C.: A simple compact fourth-order Poisson solver on polar geometry. J. Comput. Phys. 182, 337–345 (2002)
Lai, M.-C., Tseng, J.-M.: A formally fourth-order accurate compact scheme for 3D Poisson equation in cylindrical and spherical coordinates. J. Comput. Appl. Math. 201, 175–181 (2007)
Lai, M.-C., Wang, W.-C.: Fast direct solvers for Poisson equation on 2D polar and spherical geometries. Numer. Methods Partial Differ. Equ. 18, 56–68 (2002)
Larsson, E.: A domain decomposition method for the Helmholtz equation in a multilayer domain. SIAM J. Sci. Comput. 120, 1713–1731 (1999)
Li, B., Fairweather, G., Bialecki, B.: Discrete-time orthogonal spline collocation methods for vibration problems. SIAM J. Numer. Anal. 39, 2045–2065 (2002)
Liu, W.B., Shen, J.: A new efficient spectral Galerkin for singular perturbation problems. J. Sci. Comput. 11, 411–437 (1996)
Lopez, J.M., Shen, J. : An efficient spectral-projection method for the Navier–Stokes equations in cylindrical geometries. I. Axisymmetric cases. J. Comput. Phys. 139, 308–326 (1998)
Lopez, J.M., Marques, F., Shen, J.: An efficient spectral-projection method for the Navier–Stokes equations in cylindrical geometries, II. Three-dimensional cases. J. Comput. Phys. 176, 384–401 (2002)
Lou, Z.-M., Bialecki, B., Fairweather, G.: Orthogonal spline collocation methods for biharmonic problems. Numer. Math. 80, 267–303 (1998)
Louchart, O., Randriamampianina, A., Leonardi, E.: Spectral domain decomposition technique for the incompressible Navier-Stokes equations. Numer. Heat Transf., A 34, 495–518 (1998)
Lyashko, A.D., Solov’yev, S.I.: Fourier method of solution of FE systems with Hermite elements for Poisson equation. Sov. J. Numer. Anal. Math. Model. 6, 121–129 (1991)
Lynch, R.E., Rice, J.R., Thomas, D.H.: Direct solution of partial difference equations by tensor product methods. Numer. Math. 6, 185–199 (1964)
Lynch, R.E., Rice, J.R., Thomas, D.H.: Tensor product analysis of partial difference equations. Bull. Am. Math. Soc. 70, 378–384 (1964)
Maack, J.: Quadratic spline collocation for Poisson’s and biharmonic equations in the unit square. M.S. thesis, Colorado School of Mines, Golden, Colorado (2009)
Marinos, A.Th.: On a direct method for solving Helmholtz’s type equations in 3-D rectangular regions. J. Comput. Phys. 88, 62–85 (1990)
Martikainen, J., Rossi, T., Toivanen, J.: A fast direct solver for elliptic problems with a divergence constraint. Numer. Linear Algebra Appl. 9, 629–652 (2002)
Meyer, A., Rjasanow, S.: An effective direct solution method for certain boundary element equations in 3D. Math. Methods Appl. Sci. 13, 45–53 (1990)
Mittal, R.: A Fourier–Chebyshev spectral collocation method for simulating flow past spheres and spheroids. Int. J. Numer. Methods Fluids 30, 921–937 (1999)
Mittal, R.C., Gahlaut, S.: High–order finite–differences schemes to solve Poisson’s equation in polar coordinates. IMA J. Numer. Anal. 11, 261–270 (1991)
Nguyen, S., Delcarte, C.: A spectral collocation method to solve Helmholtz problems with boundary conditions involving mixed tangential and normal derivatives. J. Comput. Phys. 200, 34–49 (2004)
Osborne, M.R.: Direct methods for the solution of finite–difference approximations to partial differential equations. Comput. J. 8, 150–156 (1965/1966)
Petrova, S.: Parallel implementation of fast elliptic solver. Parallel Comput. 12, 1113–1128 (1997)
Peyret, R.: Spectral Methods for Incompressible Viscous Flow. Springer, New York (2002)
Pickering, W.M.: Some comments on the solution of Poisson’s equation using Bickley’s formula and fast Fourier transforms. J. Inst. Math. Appl. 19, 337–338 (1977)
Pickering, W.M.: An Introduction to Fast Fourier Transform Methods for Partial Differential Equations, with Applications. Research Studies Press, Wiley, New York (1986)
Pickering, W.M., Harley, P.J.: Iterative solution of the Robbins problem using FFT methods. Int. J. Comput. Math. 45, 243–257 (1992)
Pickering, W.M., Harley, P.J.: FFT solution of the Robbins problem. IMA J. Numer. Anal. 13, 215–233 (1993)
Pickering, W.M., Harley, P.J.: On Robbins boundary conditions, elliptic equations and FFT methods. J. Comput. Phys. 122, 380–383 (1995)
Plagne, L., Berthou, J.-Y.: Tensorial basis spline collocation method for Poisson’s equation. J. Comput. Phys. 157, 419–440 (2000)
Plessix, R.E., Mulder, W.A.: Separation–of–variables as a preconditioner for an iterative Helmholtz solver. Appl. Numer. Math. 44, 385–400 (2003)
Pozo, R., Remington, K.: Fast three–dimensional elliptic solvers on distributed network clusters. In: Joubert, G.R., et al. (eds.) Parallel Computing: Trends and Applications, pp. 201–208. Elsevier, Amsterdam (1994)
Rjasanow, S.: Effective algorithms with circulant–block matrices. Linear Algebra Appl. 202, 55–69 (1994)
Rjasanow, S.: Optimal preconditioner for boundary element formulation of the Dirichlet problem in elasticity. Math. Methods Appl. Sci. 18, 603–613 (1995)
Rjasanow, S.: The structure of the boundary element matrix for the three-dimensional Dirichlet problem in elasticity. Numer. Linear Algebra Appl. 5, 203–217 (1998)
Rossi, T., Toivanen, J.: A nonstandard cyclic reduction method, its variants and stability. SIAM J. Matrix Anal. Appl. 20, 628–645 (1999)
Rossi, T., Toivanen, J.: A parallel fast direct solver for block tridiagonal systems with separable matrices of arbitrary dimension. SIAM J. Sci. Comput. 20, 1778–1796 (1999)
Russell, R.D., Sun, W.: Spline collocation differentiation matrices. SIAM J. Numer. Anal. 34, 2274–2287 (1997)
Samarskii, A.A., Nikolaev, E.S.: Numerical Methods for Grid Equations. Vol. I, Direct Methods. Birkhäuser Verlag, Boston (1989)
Shen, J.: Efficient spectral-Galerkin method I. Direct solvers of second- and fourth-order equations using Legendre polynomials. SIAM J. Sci. Comput. 15, 1489–1505 (1994)
Shen, J.: Efficient spectral-Galerkin method II. Direct solvers of second- and fourth-order equations using Chebyshev polynomials. SIAM J. Sci. Comput. 16, 74–87 (1995)
Shen, J.: Efficient spectral-Galerkin methods III. Polar and cylindrical geometries. SIAM J. Sci. Comput. 18, 1583–1604 (1997)
Shen, J.: Stable and efficient spectral methods in unbounded domains using Laguerre functions. SIAM J. Numer. Anal. 38, 1113–1133 (2000)
Shen, J., Wang, L.-L.: Some recent advances on spectral methods for unbounded domains. Commun. Comput. Phys. 5, 195–241 (2009)
Smyrlis, Y.-S., Karageorghis, A.: A matrix decomposition MFS algorithm for axisymmetric potential problems. Eng. Anal. Bound. Elem. 28, 463–474 (2004)
Smyrlis, Y.-S., Karageorghis, A.: The method of fundamental solutions for stationary heat conduction problems in rotationally symmetric domains. SIAM J. Sci. Comput. 27, 1193–1512 (2006)
Stephenson, J.W.: Single cell discretizations of order two and four for biharmonic problems. J. Comput. Phys. 55, 65–80 (1984)
Sun, W.: Orthogonal collocation solution of biharmonic equations. Int. J. Comput. Math. 49, 221–232 (1993)
Sun, W.: A higher order direct method for solving Poisson’s equation on a disc. Numer. Math. 70, 501–506 (1995)
Sun, W.: Fast algorithms for high-order spline collocation systems. Numer. Math. 81, 143–160 (1998)
Sun, W., Zamani, N.G.: A fast algorithm for solving the tensor product collocation equations. J. Franklin Inst. 326, 295–307 (1989)
Swarztrauber, P.N.: The methods of cyclic reduction, Fourier analysis and the FACR algorithm for the direct solution of Poisson’s equation on a rectangle. SIAM Rev. 19, 490–501 (1977)
Swarztrauber, P.N.: Fast Poisson solvers. In: Studies in Numerical Analysis, MAA Stud. Math., vol. 24, pp. 319–370. Mathematical Association of America, Washington, DC (1984)
Swarztrauber, P.N., Sweet, R.A.: The direct solution of the discrete Poisson equation on a disk. SIAM J. Numer. Anal. 10, 900–907 (1973)
Tsangaris, T., Smyrlis, Y.-S., Karageorghis, A.: A matrix decomposition MFS algorithm for problems in hollow axisymmetric domains. J. Sci. Comput. 28, 31–50 (2006)
Tsitsas, N.L., Alivizatos, E.G., Anastassiu, H.T., Kaklamani, D.I.: Optimization of the method of auxiliary sources (MAS) for scattering by an infinite cylinder under oblique incidence. Electromagnetics 25, 39–54 (2005)
Tsitsas, N.L., Alivizatos, E.G., Anastassiu, H.T., Kaklamani, D.I.: Optimization of the method of auxiliary sources (MAS) for oblique incidence scattering by an infinite dielectric cylinder. Electr. Eng. 89, 353–361 (2007)
Tsitsas, N.L., Alivizatos, E.G., Kalogeropoulos, G.H.: A recursive algorithm for the inversion of matrices with circulant blocks. Appl. Math. Comput. 188, 877–894 (2007)
Umar, A.S.: Three-dimensional HF and TDHF calculations with the basis-spline collocation technique. In: Bottcher, C., Strayer, M.R., McGrory, J.B. (eds.) Computational Atomic and Nuclear Physics, pp. 377–390. World Scientific, Singapore (1990)
Umar, A.S., Wu, J., Strayer, M.R., Bottcher, C.: Basis-spline collocation method for the lattice solution of boundary value problems. J. Comput. Phys. 93, 426–448 (1991)
Vajteršic, M.: Algorithms for Elliptic Problems: Efficient Sequential and Parallel Solvers. Kluwer, Dordrecht (1993)
Van Loan, C.: Computational Frameworks for the Fast Fourier Transform. SIAM, Philadelphia (1992)
Vassilevski, P.: Fast algorithm for solving a linear algebraic problem with separation of variables. C. R. Acad. Bulgare Sci. 37, 305–308 (1984)
Vassilevski, P.: Fast algorithm for solving discrete Poisson equation in a rectangle. C. R. Acad. Bulgare Sci. 38, 1311–1314 (1985)
Vedy, E., Viazzo, S., Schiestel, R.: A high–order finite difference method for incompressible fluid turbulence simulations. Int. J. Numer. Methods Fluids 42, 1155–1188 (2003)
Wang, Y., Du, K., Sun, W.: Fast algorithms for the electromagnetic scattering from rectangular cavities. In: Deng, D., Jin, X.-Q., Sun, H.-W. (eds.) Recent Advances in Computational Mathematics, pp. 13–38. International Press, Somerville, Massachusetts, Higher Education Press, Beijing (2008)
Wang, Y., Du, K., Sun, W.: A second–order method for the electromagnetic scattering from a large cavity. Numer. Math. Theor. Methods Appl. 1, 357–382 (2008)
Wang, Y., Du, K., Sun, W.: Preconditioning iterative algorithm for the electromagnetic scattering from a large cavity. Numer. Linear Algebra Appl. 16, 345–363 (2009)
Zhang, Q., Shen, J., Wu, C.: A coupled Legendre–Laguerre spectral–element method for the Navier–Stokes equations in unbounded domains. J. Sci. Comput. 42, 1–22 (2010)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bialecki, B., Fairweather, G. & Karageorghis, A. Matrix decomposition algorithms for elliptic boundary value problems: a survey. Numer Algor 56, 253–295 (2011). https://doi.org/10.1007/s11075-010-9384-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-010-9384-y
Keywords
- Elliptic boundary value problems
- Poisson’s equation
- Biharmonic equation
- Matrix decomposition algorithms
- Fast Fourier transforms
- Finite difference methods
- Finite element Galerkin methods
- Spline collocation methods
- Spectral methods
- Method of fundamental solutions