GPA: Intrinsic Parallel Solver for the Discrete PDE Eigen-Problem

Abstract

A class of geometric asynchronous parallel algorithms for solving large-scale discrete PDE eigenvalues has been studied by the author (Sun in Sci China Math 41(8): 701–725, 2011; Sun in Math Numer Sin 34(1): 1–24, 2012; Sun in J Numer Methods Comput Appl 42(2): 104–125, 2021; Sun in Math Numer Sin 44(4): 433–465, 2022; Sun in Sci China Math 53(6): 859–894, 2023; Sun et al. in Chin Ann Math Ser B 44(5): 735–752, 2023). Different from traditional preconditioning algorithm with the discrete matrix directly, our geometric pre-processing algorithm (GPA) algorithm is based on so-called intrinsic geometric invariance, i.e., commutativity between the stiff matrix A and the grid mesh matrix $G{:}\,AG=GA$. Thus, the large-scale system solvers can be replaced with a much smaller block-solver as a pretreatment. In this paper, we study a sole PDE and assume G satisfies a periodic condition $G^m=I, m<< \textrm{dim}(G)$. Four special cases have been studied in this paper: two-point ODE eigen-problem, Laplace eigen-problems over L-shaped region, square ring, and 3D hexahedron. Two conclusions that “the parallelism of geometric mesh pre-transformation is mainly proportional to the number of faces of polyhedron” and “commutativity of grid mesh matrix and mass matrix is the essential condition for the GPA algorithm” have been obtained.

References

[1.] AuckenthalerT, BlumV, BungartzHJ, HuckleT, JohanniR, KrämerL, LangB, LedererH, WillemsPR. Parallel solution of partial symmetric eigenvalue problem from electronic structure calculations. Parallel Comput., 2011, 37(12): 783-794

[2.] BoffiD, BrezziF, GastaldiL. On the problem of spurious eigenvalues in the approximation of linear elliptic problems in mixed form. Math. Comput., 1999, 69(229): 121-140

[3.] Bronstein, M., Bruna J., Cohen T., Velickovic P.: Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv:2104.13478 (2021)

[4.] BronsteinM, BrunaJ, LeCunY, SzlamA, VandergheynstP. Geometric deep learning: going beyond Euclidean data. IEEE Signal Process. Mag., 2017, 34(4): 18-42

[5.] BuffaA, PerugiaT. Discontinuous Galerkin approximation of the Maxwell eigenproblem. SIAM J. Numer. Anal., 2006, 44(5): 2198-2226

[6.] CaorsiS, FernandesP, RaffettoM. On the convergence of Galerkin finite element approximation of electromagnetic eigenproblems. SIAM J. Numer. Anal., 2000, 38(2): 580-607

[7.] Chandra, R.: Conjugate Gradient Methods for Partial Differential Equations. PhD Thesis. Yale University, New Haven (1978)

[8.] ConnesA, DouglasM, SchwarzA. Noncommutative geometry and matrix theory. J. High Energy Phys., 1998, 1998(2): 003

[9.] EisenstatSC, ElmanHC, SchultzMH. Variational alternative methods for nonsymmetric systems of linear equations. SIAM J. Numer. Anal., 1983, 20(2): 345-357

[10.] Gara-PlanasMI, MagretMD. Eigenvalues of permutation matrices. Adv. Pure Math., 2015, 5: 390-394

[11.] GriffithsD. Introduction to Quantum Mechanics, 20042LondonPrentice Hall

[12.] HanJQ, LuJF, ZhouM. Solving high-dimension eigenvalue problems using deep neural networks: a diffusion Monte Carlo like approach. J. Comput. Phys., 2020, 423: 1-13

[13.] HighamNJ. Computing the polar decomposition with applications. SIAM J. Sci. Stat. Comput., 1986, 7(4): 1160-1174

[14.] HouTY, HuangD, LamKC, ZhangPC. An adaptive fast solver for a general class of positive definite matrices via energy decomposition. Multiscale Model. Simul., 2018, 16(2): 615-678

[15.] HouTY, HuangD, LamKC, ZhangZY. A fast hierarchically preconditioned eigensolver based on multiresolution matrix decomposition. Multiscale Model. Simul., 2019, 17(1): 260-306

[16.] IrgensF. Continuum Mechanics, 2008New YorkSpringer

[17.] Johanni, R., Marek, A., Lederer, H., Blum, V.: Scaling of eigenvalue solver dominated simulations. In: Mohr, B., Frings, W. (eds.) Juelich Blue Gene/P Extreme Scaling Workshop 2011, Technical Report FZJ-JSC-IB-2011-02, 27–30 (2011)

[18.] SunJC. On the minimum eigenvalue separation for matrices. Math. Numer. Sin., 1985, 7(3): 309-317

[19.] SunJC. Fourier Transforms and Orthogonal Polynomials On Non-traditional Domains, 2009HefeiUniversity of Science and Techomology Press

[20.] SunJC. On pre-transformed methods for eigen-problems, I: Yanghui-triangle transform and 2nd order PDE eigen-problems. Sci. China Math., 2011, 41(8): 701-725

[21.] SunJC. Pre-transformed methods for eigen-problems, II: eigen-structure for Laplace eigen-problems over arbitrary triangles. Math. Numer. Sin., 2012, 34(1): 1-24

[22.] SunJC. Algorithms of double-decoupling subspaces for solving FEM eigen-problems. J. Numer. Methods Comput. Appl., 2021, 42(2): 104-125

[23.] SunJC. On factorization algorithm with geometric preprocessing for discrete eigen-problems in mathematical-physics. Math. Numer. Sin., 2022, 44(4): 433-465

[24.] SunJC. Construction of intrinstic schmemes for eigen-computation based on polyhedron grid matrix in 3-D. Sci. China Math., 2023, 53(6): 859-894

[25.] SunJC, CaoJW, ZhangY, ZhaoHT. Commutation of geometry-grids and fast discrete PDE eigen-solver GPA. Chin. Ann. Math. Ser. B, 2023, 44(5): 735-752

[26.] WilkinsonJH. The Algebraic Eigenvalue Problem, 1965OxfordClaredon Press

[27.] ZhouYL. Difference schemes with intrinsic parallelism for quasilinear parabolic systems. Sci. China Math., 1997, 40: 270-278