Geodesic
Block tensor conjugate gradient-type method for Rayleigh quotient minimization in two-dimensional case
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 5, pp. 787-804 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A method for solving a partial algebraic eigenvalues problem is constructed. It exploits tensor structure of eigenvectors in two-dimensional case. For a symmetric matrix represented in tensor format, the method finds low-rank approximations to the eigenvectors corresponding to the smallest eigenvalues. For sparse matrices, execution time and required memory for the proposed method are proportional to the square root of miscellaneous overall number of unknowns, whereas this dependence is usually linear. To maintain tensor structure of vectors at each iteration step, low-rank approximations are performed, which introduces errors into the original method. Nevertheless, the new method was proved to converge. Convergence rate estimates are obtained for various tensor modifications of the abstract one-step method. It is shown how the convergence of a multistep method can be derived from the convergence of the corresponding one-step method. Several modifications of the method with an low-rank approximation techniques were implemented on the basis of the block conjugate gradient method. Their performance is compared on numerical examples. 
@article{ZVMMF_2010_50_5_a0,
     author = {O. S. Lebedeva},
     title = {Block tensor conjugate gradient-type method for {Rayleigh} quotient minimization in two-dimensional case},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {787--804},
     year = {2010},
     volume = {50},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_5_a0/}
}
TY  - JOUR
AU  - O. S. Lebedeva
TI  - Block tensor conjugate gradient-type method for Rayleigh quotient minimization in two-dimensional case
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2010
SP  - 787
EP  - 804
VL  - 50
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_5_a0/
LA  - ru
ID  - ZVMMF_2010_50_5_a0
ER  - 
%0 Journal Article
%A O. S. Lebedeva
%T Block tensor conjugate gradient-type method for Rayleigh quotient minimization in two-dimensional case
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2010
%P 787-804
%V 50
%N 5
%U http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_5_a0/
%G ru
%F ZVMMF_2010_50_5_a0
O. S. Lebedeva. Block tensor conjugate gradient-type method for Rayleigh quotient minimization in two-dimensional case. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 5, pp. 787-804. http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_5_a0/

[1] Saad Y., “Numerical methods for large eigenvalue problems”, Algorithms and Architectures for Advanced Scient. Comput., Manchester Univ. Press, Manchester, 1992 | MR | Zbl

[2] Parlett B., Simmetrichnaya problema sobstvennykh znachenii, Mir, M., 1983 | MR | Zbl

[3] Pan V. Y., Rami Y., Wang X., “Structured matrices and Newton's iteration: unified approach”, Linear Algebra and Applic., 343 (2002), 233–265 | DOI | MR | Zbl

[4] Olshevsky V., Oseledets I., Tyrtyshnikov E., “Superfast inversion of two-level Toeplitz matrices using Newton iteration and tensor-displacement structure”, Recent Advances in Matrix and Operator Theory, 179, Birkhäuser, Basel, 2008, 229–240 | MR | Zbl

[5] Oseledets I. V., Tyrtyshnikov E. E., “Priblizhennoe obraschenie matrits pri reshenii gipersingulyarnogo uravneniya”, Zh. vychisl. matem. i matem. fiz., 45:2 (2005), 315–326 | MR | Zbl

[6] Hackbusch W., Khoromskij B. N., Tyrtyshnikov E. E., “Approximate iterations for structured matrices”, Numer. Math., 109:3 (2008), 365–383 | DOI | MR | Zbl

[7] Oseledets I., Savostyanov D., Tyrtyshnikov E., “Linear algebra for tensor problems”, Computing, 85:3 (2009), 169–188 | DOI | MR | Zbl

[8] Tyrtyshnikov E., “Preservation of linear constraints in approximation of tensors”, Numer. Math. Theor. Meth. Appl., 2:4 (2009), 421–426 | MR | Zbl

[9] Tyrtyshnikov E. E., “Tensor approximations of matrices generated by asymptotically smooth functions”, Matem. Sb., 194:6 (2003), 147–160 | MR | Zbl

[10] Knyazev A. V., “Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method”, SIAM J. Sci. Comput., 23:2 (2001), 517–541 | DOI | MR | Zbl

[11] Lashuk I., Argentati M., Ovtchinnikov E., Knyazev A., “Preconditioned eigensolver LOBPCG in hypre and PETSc”, Domain Decomposition Methods in Sci. and Eng. XVI, 55, Springer, Berlin, 2007, 635–642 | MR

[12] D'yakonov E. G., Knyazev A. V., “A group iteration method for finding the lowest eigenvalues”, Vestnik Moskov. Univ. Ser. XV. Vychisl. Matem. and Kibernetica, 1982, no. 2, 29–34 ; 81 | MR

[13] Hetmaniuk U., Lehoucq R., “Basis selection in LOBPCG”, J. Comput. Phys., 218:1 (2006), 324–332 | DOI | MR | Zbl