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

Xing Li; Chungen Shen; Lei-Hong Zhang

doi:10.3934/naco.2018025

Article Contents

2018, Volume 8, Issue 4: 389-412. Doi: 10.3934/naco.2018025

This issue Previous Article Next Article Optimization problems with orthogonal matrix constraints

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

1.
School of Mathematics, Shanghai University of Finance and Economics, 777 Guoding Road, Yangpu District, Shanghai, 200433, People's Republic of China
2.
College of Science, University of Shanghai for Science and Technology, 334 Jungong Road, Yangpu District, Shanghai 200093, China
3.
School of Mathematics and Shanghai Key Laboratory of Financial Information Technology, Shanghai University of Finance and Economics, 777 Guoding Road, Yangpu District, Shanghai, 200433, People's Republic of China

^* Corresponding author: Lei-Hong Zhang
^* Corresponding author: Lei-Hong Zhang

Received: February 2017

Revised: August 2018

Published: September 2018

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

Abstract

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.

Keywords:

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

Citation:

FullText(HTML)

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$

Download: Full-size image PowerPoint slide

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{cg_tol}$	$\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{cg_tol}$		$\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{n}$	$\textsf{cond}(K)$	$k$		$\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{n}$	$\textsf{cond}$ ($K$)	$k$		$\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

Related Papers

Cited by

References

[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. Brabec, L. Lin, M. Shao, N. Govind, C. Yang, Y. 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. Flaschka, W.-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. Johnson, Matrix 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. Li, R.-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. Rocca, Z. Bai, R.-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. Rocca, R. Gebauer, Y. 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. Teng, Y. 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. Zhang, W. 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. Zhang, J. 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.