[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Incomplete double-cone factorizations of centrosymmetric matrices arising in spectral methods

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

We develop structure-preserving incomplete LU type factorizations for preconditioning centrosymmetric matrices and use them to numerically solve centrosymmetric and nearly centrosymmetric linear systems arising from spectral methods for partial differential equations. Our algorithm builds in part on direct solution techniques previously developed for this type of linear systems, featuring double-cone factorizations. We illustrate our findings on discretizations of model problems involving the Poisson, diffusion, Helmholtz, and biharmonic equations in one, two, and three dimensions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Data availability

Not applicable

Code availability

The numerical code for solving the problems described in this paper is available at tinyurl.com/2uf3645d.

References

  1. Weaver, J.R.: Centrosymmetric (cross-symmetric) matrices, their basic properties, eigenvalues, and eigenvectors. Amer Math Monthly. 92(10), 711–7 (1985)

    MathSciNet  Google Scholar 

  2. Kimura, M.: Some problems of stochastic processes in genetics. Ann Math Statist. 28, 882–901 (1957)

    MathSciNet  Google Scholar 

  3. Datta, L., Morgera, S.D.: On the reducibility of centrosymmetric matrices, applications in engineering problems. Circuits Systems Signal Process. 8(1), 71–96 (1989)

    MathSciNet  Google Scholar 

  4. Gaudreau P, Safouhi H. Centrosymmetric matrices in the Sinc collocation method for Sturm-Liouville problems. EPJ Web of Conferences, Mathematical Modeling and Computational Physics (MMCP 2015). 2016;108:01004

  5. Chan, R.H., Ng, M.K.: Conjugate gradient methods for Toeplitz systems. SIAM Rev. 38(3), 427–82 (1996)

    MathSciNet  Google Scholar 

  6. Chan RH, Jin XQ. An introduction to iterative Toeplitz solvers. vol. 5 of Fundamentals of Algorithms. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; 2007

  7. Chan, R.H.: Circulant preconditioners for Hermitian Toeplitz systems. SIAM J Matrix Anal Appl. 10(4), 542–50 (1989)

    MathSciNet  Google Scholar 

  8. Chan, R.H., Ng, K.P.: Toeplitz preconditioners for Hermitian Toeplitz systems. Linear Algebra Appl. 190, 181–208 (1993)

    MathSciNet  Google Scholar 

  9. Pestana, J.: Preconditioners for symmetrized Toeplitz and multilevel Toeplitz matrices. SIAM J Matrix Anal Appl. 40(3), 870–87 (2019)

    MathSciNet  Google Scholar 

  10. Mazza, M., Pestana, J.: Spectral properties of flipped Toeplitz matrices and related preconditioning. BIT. 59(2), 463–82 (2019)

    MathSciNet  Google Scholar 

  11. Ng, M.K., Sun, H.W., Jin, X.Q.: Recursive-based PCG methods for Toeplitz systems with nonnegative generating functions. SIAM J Sci Comput. 24(5), 1507–29 (2003)

    MathSciNet  Google Scholar 

  12. Heinig, G.: Chebyshev-Hankel matrices and the splitting approach for centrosymmetric Toeplitz-plus-Hankel matrices. Linear Algebra Appl. 327(1–3), 181–96 (2001)

    MathSciNet  Google Scholar 

  13. Heinig G, Rost K. Fast algorithms for centro-symmetric and centro-skewsymmetric Toeplitz-plus-Hankel matrices. Numer Algorithms. 2003;33(1-4):305-17. International Conference on Numerical Algorithms, Vol. I (Marrakesh, 2001)

  14. Heinig G, Rost K. Split algorithms for centrosymmetric Toeplitz-plus-Hankel matrices with arbitrary rank profile. In: The extended field of operator theory. vol. 171 of Oper. Theory Adv. Appl. Birkhäuser, Basel; 2007. p. 129-46

  15. Tian, Z., Gu, C.: The iterative methods for centrosymmetric matrices. Appl Math Comput. 187(2), 902–11 (2007)

    MathSciNet  Google Scholar 

  16. Andrew, A.L.: Eigenvectors of certain matrices. Linear Algebra Appl. 7, 151–62 (1973)

    MathSciNet  Google Scholar 

  17. Tao, D., Yasuda, M.: A spectral characterization of generalized real symmetric centrosymmetric and generalized real symmetric skew-centrosymmetric matrices. SIAM journal on matrix analysis and applications. 23(3), 885–95 (2002)

    MathSciNet  Google Scholar 

  18. Mackey, D.S., Mackey, N., Tisseur, F.: Structured tools for structured matrices. Electron J Linear Algebra. 10, 106–45 (2003)

    MathSciNet  Google Scholar 

  19. Trench, W.F.: Characterization and properties of matrices with generalized symmetry or skew symmetry. Linear Algebra Appl. 377, 207–18 (2004)

    MathSciNet  Google Scholar 

  20. Mackey, D.S., Mackey, N., Dunlavy, D.M.: Structure preserving algorithms for perplectic eigenproblems. Electron J Linear Algebra. 13, 10–39 (2005)

    MathSciNet  Google Scholar 

  21. Andrew, A.L.: Solution of equations involving centrosymmetric matrices. Technometrics. 15(2), 405–7 (1973)

    Google Scholar 

  22. Abu-Jeib IT. Algorithms for centrosymmetric and skew-centrosymmetric matrices. Missouri journal of mathematical sciences. 2006;18(1)

  23. El-Mikkawy, M., Atlan, F.: On solving centrosymmetric linear systems. Applied mathematics (Irvine, Calif). 4(12A), 21–32 (2013)

    Google Scholar 

  24. Burnik, K.: A structure-preserving QR factorization for centrosymmetric real matrices. Linear Algebra Appl. 484, 356–78 (2015)

    MathSciNet  Google Scholar 

  25. Steele, A., Yalim, J., Welfert, B.: QX factorization of centrosymmetric matrices. Appl Numer Math. 134, 11–6 (2018)

    MathSciNet  Google Scholar 

  26. Lv P, Zheng B. Perturbation analysis for the QX factorization for centrosymmetric matrices. Linear and multilinear algebra. 2020:1-24

  27. Canuto, C., Hussaini, M.Y., Quarteroni, A., Zang, T.A.: Spectral methods, fundamentals in single domains. Scientific computation. Springer-Verlag, Berlin (2006)

    Google Scholar 

  28. Shen J, Tang T, Wang LL. Spectral methods: algorithms, analysis and applications. vol. 41 of Springer series in computational mathematics. 1st ed. Berlin, Heidelberg: Springer-Verlag; 2011

  29. Melman, A.: Symmetric centrosymmetric matrix-vector multiplication. Linear Algebra and its Applications. 320(1), 193–8 (2000)

    MathSciNet  Google Scholar 

  30. Fassbender, H., Ikramov, K.D.: Computing matrix-vector products with centrosymmetric and centrohermitian matrices. Linear Algebra Appl. 364, 235–41 (2003)

    MathSciNet  Google Scholar 

  31. Lui SH. Numerical analysis of partial differential equations. Pure and Applied Mathematics (Hoboken). John Wiley & Sons, Inc., Hoboken, NJ; 2011

  32. Lui, S.H., Nataj, S.: Spectral collocation in space and time for linear PDEs. J Comput Phys. 424(109843), 22 (2021)

    MathSciNet  Google Scholar 

  33. Ascher, U.M., Greif, C.: A first course in numerical methods. Society for Industrial and Applied Mathematics, Philadelphia (2011)

    Google Scholar 

  34. Golub, G.H., Van Loan, C.F.: Matrix computations, 4th edn. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD (2013)

    Google Scholar 

  35. Demmel, J.W.: Applied numerical linear algebra. Society for Industrial and Applied Mathematics, Philadelphia (1997)

    Google Scholar 

  36. Orszag, S.A.: Spectral methods for problems in complex geometries. Journal of Computational Physics. 37(1), 70–92 (1980)

    ADS  MathSciNet  Google Scholar 

  37. Haldenwang, P., Labrosse, G., Abboudi, S., Deville, M.: Chebyshev 3-D spectral and 2-D pseudospectral solvers for the Helmholtz equation. Journal of computational physics. 55(1), 115–28 (1984)

    ADS  MathSciNet  Google Scholar 

  38. Canuto, C., Quarteroni, A.: Preconditioned minimal residual methods for Chebyshev spectral calculations. Journal of computational physics. 60(2), 315–37 (1985)

    ADS  MathSciNet  Google Scholar 

  39. Deville, M., Mund, E.: Chebyshev pseudospectral solution of second-order elliptic equations with finite element preconditioning. Journal of computational physics. 60(3), 517–33 (1985)

    ADS  MathSciNet  Google Scholar 

  40. Quarteroni, A., Zampieri, E.: Finite element preconditioning for Legendre spectral collocation approximations to elliptic equations and systems. SIAM journal on numerical analysis. 29(4), 917–36 (1992)

    MathSciNet  Google Scholar 

  41. Wang, L.L., Samson, M.D., Zhao, X.: A well-conditioned collocation method using a pseudospectral integration matrix. SIAM Journal on Scientific Computing. 36(3), A907-29 (2014)

    MathSciNet  Google Scholar 

  42. McCoid, C., Trummer, M.R.: Preconditioning of spectral methods via Birkhoff interpolation. Numerical algorithms. 79(2), 555–73 (2018)

    MathSciNet  Google Scholar 

  43. Xiang, H., Grigori, L.: Kronecker product approximation preconditioners for convection-diffusion model problems. Numer Linear Algebra Appl. 17(4), 691–712 (2010)

    MathSciNet  Google Scholar 

  44. Pazner W, Persson PO. Approximate tensor-product preconditioners for very high order discontinuous Galerkin methods. Journal of computational physics. 2018;354(C):344-69

  45. Meijerink, J.A., van der Vorst, H.A.: Guidelines for the usage of incomplete decompositions in solving sets of linear equations as they occur in practical problems. J Comput Phys. 44(1), 134–55 (1981)

    ADS  MathSciNet  Google Scholar 

  46. Saad, Y.: Iterative methods for sparse linear systems, 2nd edn. SIAM, Philadelphia (2003)

    Google Scholar 

  47. Funaro, D., Heinrichs, W.: Some results about the pseudospectral approximation of one-dimensional fourth-order problems. Numer Math. 58(4), 399–418 (1990)

    MathSciNet  Google Scholar 

  48. Heinrichs, W.: A stabilized treatment of the biharmonic operator with spectral methods. SIAM J Sci Statist Comput. 12(5), 1162–72 (1991)

    MathSciNet  Google Scholar 

  49. Ernst OG, Gander MJ. Why it is difficult to solve Helmholtz problems with classical iterative methods. In: Numerical Analysis of Multiscale Problems. Lecture Notes in Computational Science and Engineering. Berlin, Heidelberg: Springer; 2011. p. 325-63

  50. Sinkhorn, R., Knopp, P.: Concerning nonnegative matrices and doubly stochastic matrices. Pacific J Math. 21, 343–8 (1967)

    MathSciNet  Google Scholar 

  51. Knight, P.A., Ruiz, D., Uçar, B.: A symmetry preserving algorithm for matrix scaling. SIAM J Matrix Anal Appl. 35(3), 931–55 (2014)

    MathSciNet  Google Scholar 

  52. Saad Y. ITSOL v2.0, Iterative solvers packages. 2017. Available at https://www-users.cse.umn.edu/~saad/software/ITSOL/index.html

Download references

Acknowledgements

The authors thank the anonymous referees for their careful reading and valuable suggestions.

Funding

This work was partially funded by Natural Sciences and Engineering Research Council of Canada (NSERC).

Author information

Author notes

  1. Chen Greif, Sarah Nataj and Manfred Trummer contributed equally to this work.

Authors and Affiliations

  1. Department of Computer Science, University of British Columbia, Vancouver, BC, Canada

    Chen Greif & Sarah Nataj

  2. Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada

    Sarah Nataj & Manfred Trummer

Authors
  1. Chen Greif
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sarah Nataj
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Manfred Trummer
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

The authors contributed equally to this work.

Corresponding author

Correspondence to Sarah Nataj.

Ethics declarations

Ethics approval

Not applicable

Consent to participate

Not applicable

Consent for publication

Not applicable

Conflict of interest

The authors declare no competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Greif, C., Nataj, S. & Trummer, M. Incomplete double-cone factorizations of centrosymmetric matrices arising in spectral methods. Numer Algor 95, 1359–1386 (2024). https://doi.org/10.1007/s11075-023-01612-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-023-01612-y

Keywords

Mathematics Subject Classification (2010)