\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

A projected preconditioned conjugate gradient method for the linear response eigenvalue problem

  • * Corresponding author: Lei-Hong Zhang

    * Corresponding author: Lei-Hong Zhang
The third author is supported by NSF grant NSFC-11671246, NSFC-91730303 and NSFC-11371102.
Abstract / Introduction Full Text(HTML) Figure(1) / Table(7) Related Papers Cited by
  • The linear response eigenvalue problem aims at computing a few smallest positive eigenvalues together with the associated eigenvectors of a special Hamiltonian matrix and plays an important role for estimating the excited states of physical systems. A subspace version of the Thouless minimization principle was established by Bai and Li (SIAM J. Matrix Anal. Appl., 33:1075-1100, 2012) which characterizes the desired eigenpairs as its solution. In this paper, we propose a Projected Preconditioned Conjugate Gradient ($\texttt{PPCG_lrep}$) method to solve this subspace version of Thouless's minimization directly. We show that $\texttt{PPCG_lrep}$ is an efficient implementation of the inverse power iteration and can be performed in parallel. It also enjoys several properties including the monotonicity and constraint preservation in the Thouless minimization principle. Convergence of both eigenvalues and eigenvectors are established and numerical experiences on various problems are reported.

    Mathematics Subject Classification: Primary: 65F15, 65F30; Secondary: 15A18.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 5.1.  Relative error of $\breve{\lambda}_i^{(j)}$ w.r.t. outer loop iteration $j$ for the case $n = 500$ and $k = 4$

    Table 5.1.  The CPU time(s) for the case $n = 500$ and $k = 4$

    $\textsf{cg_tol}$ Using PCG for (3.3) and (3.4) $\texttt{PPCG_lrep}$
    $\textsf{Iden}$ $\textsf{Diag}$ $\textsf{Chol}$ $\textsf{Iden}$ $\textsf{Diag}$ $\textsf{Chol}$ $\textsf{SSOR}$
    $10^{-10}$ 78.31 350.15 3.06 6.60 5.92 0.28 27.21
    $10^{-9}$ 74.53 342.30 2.61 5.99 4.74 0.22 22.09
    $10^{-8}$ 74.22 345.08 3.06 5.31 3.94 0.21 17.72
    $10^{-7}$ 74.38 339.19 3.48 4.55 3.12 0.20 13.35
    $10^{-6}$ 73.48 338.52 3.62 3.84 2.14 0.19 9.12
    $10^{-5}$ 72.76 334.73 2.94 3.08 1.49 0.16 3.53
     | Show Table
    DownLoad: CSV

    Table 5.2.  Numerical results of $\texttt{PPCG_lrep}$ for $n = 500$ and $k = 4$

    $\textsf{cg_tol}$ $\texttt{PPCG_lrep}$
    $\textsf{Iden}$ $\textsf{Diag}$ $\textsf{Chol}$ $\textsf{SSOR}$
    $10^{-10}$ RESeig $4.29 \times 10^{-9}$ $2.33 \times 10^{-7}$ $1.72 \times 10^{-8}$ $2.43 \times 10^{-7}$
    outer iter. 25 25 25 25
    inner iter. 14831 11484 50 8232
    $10^{-9}$ RESeig $5.77 \times 10^{-9}$ $2.55 \times 10^{-6}$ $1.72 \times 10^{-8}$ $2.37 \times 10^{-6}$
    outer iter. 25 21 25 25
    inner iter. 14321 9500 50 6651
    $10^{-8}$ RESeig $5.30 \times 10^{-8}$ $2.37 \times 10^{-5}$ $5.39 \times 10^{-8}$ $1.93 \times 10^{-5}$
    outer iter. 25 21 25 21
    inner iter. 12699 7913 47 5337
    $10^{-7}$ RESeig $5.33 \times 10^{-7}$ $2.68 \times 10^{-4}$ $5.27 \times 10^{-7}$ $1.91 \times 10^{-4}$
    outer iter. 25 17 25 21
    inner iter. 10906 6151 41 4004
    $10^{-6}$ RESeig $5.38 \times 10^{-6}$ $3.60 \times 10^{-3}$ $5.16 \times 10^{-6}$ $2.25 \times 10^{-3}$
    outer iter. 21 13 25 17
    inner iter. 9114 4222 35 2783
    $10^{-5}$ RESeig $5.87 \times 10^{-5}$ $1.87 \times 10^{-2}$ $5.05 \times 10^{-5}$ $1.11 \times 10^{-1}$
    outer iter. 21 13 21 9
    inner iter. 7370 2930 29 1057
     | Show Table
    DownLoad: CSV

    Table 5.3.  The sparse matrices $K$ and $M$

    Problem $n$ $K$ $M$
    SPARSE TEST 1 10001 bloweybq ted_B
    SPARSE TEST 2 9604 fv1 finan512
     | Show Table
    DownLoad: CSV

    Table 5.4.  Numerical results of $\texttt{PPCG_lrep}$ for sparse problems

    $\textsf{Iden}$ $\textsf{Diag}$ $\textsf{IChol}$ $\textsf{SSOR}$
    SPARSE TEST 1 CPU time(s) 157.10 120.77 0.86 75.80
    outer iter. 69 49 9 13
    inter iter. 18926 12769 22 2120
    SPARSE TEST 2 CPU time(s) 73.79 52.19 55.46 78.38
    outer iter. 473 477 473 473
    inter iter. 8012 4599 1076 2432
     | Show Table
    DownLoad: CSV

    Table 5.5.  Numerical results of $\texttt{PPCG_lrep}$ and $\texttt{B4dSD}$ for the case (5.1)

    $\textsf{n}$ $\textsf{cond}(K)$ $k$ $\texttt{PPCG_lrep}$ $\texttt{B4dSD}$
    $\textsf{Iden}$ $\textsf{Diag}$ $\textsf{Chol}$ $\textsf{Iden}$ $\textsf{Chol}$ $\textsf{CG}$
    1000 $1.57 \times 10^{7}$ 4 CPU times(s) 11.07 7.23 0.32 44.35 0.12 76.33
    RESeig $3.49\times 10^{-6}$ $8.02\times 10^{-3}$ $1.21\times 10^{-6}$ $8.90\times 10^{-1}$ $7.34\times 10^{-4}$ $1.98\times 10^{-4}$
    outer iter. 9 9 9 5000 3 504
    inner iter. 6027 3526 7 - - -
    10 CPU times(s) 57.48 18.94 1.23 102.43 0.15 68.64
    RESeig $5.67\times 10^{-7}$ $8.80\times 10^{-4}$ $5.12\times 10^{-6}$ $5.29\times 10^{-1}$ $1.22\times 10^{-2}$ $2.54\times 10^{-2}$
    outer iter. 33 17 25 5000 3 189
    inner iter. 19932 5735 41 - - -
    1500 $4.98\times 10^{9}$ 4 CPU times(s) 31.55 17.26 0.78 86.22 0.26 256.26
    RESeig $9.65\times 10^{-6}$ $9.40\times 10^{-3}$ $4.62\times 10^{-6}$ $9.45\times 10^{-1}$ $1.82\times 10^{-3}$ $3.94\times 10^{-2}$
    outer iter. 9 9 9 5000 3 791
    inner iter. 8207 4333 9 - - -
    10 CPU times(s) 175.69 65.56 2.44 143.45 0.30 146.67
    RESeig $8.59\times 10^{-7}$ $1.65\times 10^{-3}$ $3.53\times 10^{-6}$ $7.36\times 10^{-1}$ $1.53\times 10^{-2}$ $1.56\times 10^{-2}$
    outer iter. 29 17 25 5000 3 186
    inner iter. 30099 10075 37 - - -
    2000 $3.87\times 10^{7}$ 4 CPU times(s) 141.18 53.60 1.84 145.82 0.57 766.27
    RESeig $4.42\times 10^{-5}$ $2.67\times 10^{-1}$ $1.08\times 10^{-5}$ $9.63\times 10^{-1}$ $1.95\times 10^{-2}$ $8.04\times 10^{-2}$
    outer iter. 17 13 13 5000 3 1361
    inner iter. 21875 7925 13 - - -
    10 CPU times(s) 507.23 150.00 8.05 243.64 0.59 968.64
    RESeig $3.13\times 10^{-6}$ $7.88\times 10^{-3}$ $7.65\times 10^{-6}$ $8.32\times 10^{-1}$ $1.39\times 10^{-2}$ $3.39\times 10^{-3}$
    outer iter. 37 17 41 5000 3 430
    inner iter. 51725 14066 67 - - -
     | Show Table
    DownLoad: CSV

    Table 5.6.  Numerical results of $\texttt{PPCG_lrep}$ and $\texttt{B4dSD}$ for the case (5.2)

    $\textsf{n}$ $\textsf{cond}$ ($K$) $k$ $\texttt{PPCG_lrep}$ $\texttt{B4dSD}$
    $\textsf{Iden}$ $\textsf{Diag}$ $\textsf{Chol}$ $\textsf{Iden}$ $\textsf{Chol}$ $\textsf{CG}$
    1000 98.98 4 CPU times(s) 1.07 1.30 1.46 15.44 1.13 9.76
    RESeig $9.49\times 10^{-4}$ $5.35\times 10^{-4}$ $3.48\times 10^{-5}$ $8.97\times 10^{-5}$ $7.88\times 10^{-5}$ $6.95\times 10^{-5}$
    outer iter. 29 29 37 1820 66 66
    inner iter. 514 595 61 - - -
    10 CPU times(s) 1.10 1.45 1.22 12.06 0.86 11.90
    RESeig $6.55\times 10^{-4}$ $2.57\times 10^{-4}$ $2.11\times 10^{-5}$ $5.40\times 10^{-5}$ $3.47\times 10^{-4}$ $2.35\times 10^{-4}$
    outer iter. 21 21 25 846 33 33
    inner iter. 326 385 41 - - -
    1500 99.47 4 CPU times(s) 1.41 1.93 3.89 27.96 2.45 20.91
    RESeig $2.75\times 10^{-3}$ $1.43\times 10^{-3}$ $1.12\times 10^{-4}$ $4.23\times 10^{-5}$ $4.92\times 10^{-5}$ $4.16\times 10^{-5}$
    outer iter. 21 25 45 1626 64 65
    inner iter. 302 404 77 - - -
    10 CPU times(s) 2.27 2.76 3.43 24.54 2.11 30.83
    RESeig $1.00\times 10^{-3}$ $5.70\times 10^{-4}$ $5.79\times 10^{-5}$ $1.75\times 10^{-3}$ $5.43\times 10^{-3}$ $2.69\times 10^{-3}$
    outer iter. 21 21 33 852 40 39
    inner iter. 321 376 55 - - -
    2000 84.74 4 CPU times(s) 2.96 3.54 12.78 62.44 5.00 44.36
    RESeig $7.96\times 10^{-3}$ $6.55\times 10^{-3}$ $1.55\times 10^{-3}$ $2.28\times 10^{-3}$ $1.85\times 10^{-3}$ $1.97\times 10^{-3}$
    outer iter. 25 25 85 2128 78 80
    inner iter. 378 460 157 - - -
    10 CPU times(s) 4.54 5.91 7.50 46.85 3.93 57.14
    RESeig $9.35\times 10^{-4}$ $4.74\times 10^{-4}$ $4.61\times 10^{-5}$ $4.33\times 10^{-4}$ $1.42\times 10^{-4}$ $1.43\times 10^{-4}$
    outer iter. 25 29 41 960 42 42
    inner iter. 396 488 69 - - -
     | Show Table
    DownLoad: CSV

    Table 5.7.  Numerical results of $\texttt{PPCGp_lrep} $ and $\texttt{PPCGb_lrep}$

    Problem $\texttt{PPCGp_lrep}$ $\texttt{PPCGb_lrep}$
    ${\rm Na}_2$ $\textsf{Iden}$ $\textsf{Diag}$ $\textsf{Iden}$ $\textsf{Diag}$
    CPU time(s) 17.53 15.90 29.48 27.64
    RESeig $1.64\times10^{-6}$ $1.72\times10^{-6}$ $1.64\times10^{-6}$ $1.67\times10^{-6}$
    outer iter. 73 73 73 73
    inner iter. 1818 1533 2411 2048
    ${\rm SiH}_4$ CPU time(s) 105.94 77.08 142.84 103.59
    RESeig $3.20\times10^{-6}$ $3.10\times10^{-6}$ $3.11\times10^{-6}$ $3.04\times10^{-6}$
    outer iter. 121 121 121 121
    inner iter. 1113 722 1055 677
     | Show Table
    DownLoad: CSV
  • [1] Z. Bai and R. C. Li, Minimization principle for linear response eigenvalue problem, Ⅰ: Theory, SIAM J. Matrix Anal. Appl., 33 (2012), 1075-1100.  doi: 10.1137/110838960.
    [2] Z. Bai and R. C. Li, Minimization principles for the linear response eigenvalue problem Ⅱ: Computation, SIAM J. Matrix Anal. Appl., 34 (2013), 392-416.  doi: 10.1137/110838972.
    [3] J. BrabecL. LinM. ShaoN. GovindC. YangY. Saad and E.G. Ng, Efficient algorithms for estimating the absorption spectrum within linear response TDDFT, J. Chem. Theory Comput., 11 (2015), 5197-5208.  doi: 10.1021/acs.jctc.5b00887.
    [4] T. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Softw., 38 (2011), 1-25.  doi: 10.1145/2049662.2049663.
    [5] U. FlaschkaW.-W. Lin and J.-L. Wu, A KQZ algorithm for solving linear-response eigenvalue equations, Linear Algebra Appl., 165 (1992), 93-123.  doi: 10.1016/0024-3795(92)90231-X.
    [6] R. A. Horn and  C. R. JohnsonMatrix Analysis, Cambridge University Press, Cambridge, 1985.  doi: 10.1017/CBO9780511810817.
    [7] A.V. Knyazev and M.E. Argentati, Principal angles between subspaces in an $A$-based scalar product: Algorithms and perturbation estimates, SIAM J. Matrix Anal. Appl., 23 (2002), 2008-2040.  doi: 10.1137/S1064827500377332.
    [8] T. LiR.-C. Li and W.-W. Lin, A symmetric structure-preserving ΓQR algorithm for linear response eigenvalue problems, Linear Algebra Appl., 520 (2017), 191-214.  doi: 10.1016/j.laa.2017.01.005.
    [9] J. Nocedal and S. Wright, Numerical Optimization, Springer, 2nd edition, 2006.
    [10] D. RoccaZ. BaiR.-C. Li and G. Galli, A block variational procedure for the iterative diagonalization of non-Hermitian random-phase approximation matrices, J. Chem. Phys., 136 (2012), 034111.  doi: 10.1063/1.3677667.
    [11] D. RoccaR. GebauerY. Saad and S. Baroni, Turbo charging time-dependent density-functional theory with Lanczos chains, J. Chem. Phys., 128 (2008), 928-934.  doi: 10.1063/1.2899649.
    [12] E. Runge and E. K. U. Gross, Density-functional theory for time-dependent systems, Phys. Rev. Lett., 52 (1984), 997-1000.  doi: 10.1103/PhysRevLett.52.997.
    [13] Z. Teng and R.-C. Li, Convergence analysis of Lanczos-type methods for the linear response eigenvalue problem, J. Comput. Appl. Math., 247 (2013), 17-33.  doi: 10.1016/j.cam.2013.01.003.
    [14] Z. TengY. Zhou and R.-C. Li, A block Chebyshev-Davidson method for linear response eigenvalue problems, Adv. in Comput. Math., 42 (2016), 1103-1128.  doi: 10.1007/s10444-016-9455-2.
    [15] D.J. Thouless, Vibrational states of nuclei in the random phase approximation, Nuclear Physics, 22 (1961), 78-95.  doi: 10.1016/0029-5582(61)90364-9.
    [16] D. J. Thouless, The Quantum Mechanics of Many-Body Systems, Academic, 1972.
    [17] L. H. ZhangW. W. Lin and R. C. Li, Backward perturbation analysis and residual-based error bounds for the linear response eigenvalue problem, BIT, 55 (2015), 869-896.  doi: 10.1007/s10543-014-0519-8.
    [18] L. H. ZhangJ. Xue and R. C. Li, Rayleigh-Ritz approximation for the linear response eigenvalue problem, SIAM J. Matrix Anal. Appl., 35 (2014), 765-782.  doi: 10.1137/130946563.
  • 加载中

Figures(1)

Tables(7)

SHARE

Article Metrics

HTML views(1969) PDF downloads(410) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return