Geodesic
An efficient truncated SVD of large matrices based on the low-rank approximation for inverse geophysical problems
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 12 (2015), pp. 592-609.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we propose a new algorithm to compute a truncated singular value decomposition (T-SVD) of the Born matrix based on a low-rank arithmetic. This algorithm is tested in the context of acoustic media. Theoretical background to the low-rank SVD method is presented: the Born matrix of an acoustic problem can be approximated by a low-rank approximation derived thanks to a kernel independent multipole expansion. The new algorithm to compute T-SVD approximation consists of four steps, and they are described in detail. The largest singular values and their left and right singular vectors can be approximated numerically without performing any operation with the full matrix. The low-rank approximation is computed due to a dynamic panel strategy of cross approximation (CA) technique. At the end of the paper, we present a numerical experiment to illustrate the efficiency and precision of the algorithm proposed.
Keywords: SVD algorithm, cross approximation (CA), low-rank approximation, high-performance computing, parallel computations.
Mots-clés : Born matrix 
@article{SEMR_2015_12_a73,
     author = {S. A. Solovyev and S. Tordeux},
     title = {An efficient truncated {SVD} of large matrices based on the low-rank approximation for inverse geophysical problems},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {592--609},
     publisher = {mathdoc},
     volume = {12},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2015_12_a73/}
}
TY  - JOUR
AU  - S. A. Solovyev
AU  - S. Tordeux
TI  - An efficient truncated SVD of large matrices based on the low-rank approximation for inverse geophysical problems
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2015
SP  - 592
EP  - 609
VL  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2015_12_a73/
LA  - en
ID  - SEMR_2015_12_a73
ER  - 
%0 Journal Article
%A S. A. Solovyev
%A S. Tordeux
%T An efficient truncated SVD of large matrices based on the low-rank approximation for inverse geophysical problems
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2015
%P 592-609
%V 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2015_12_a73/
%G en
%F SEMR_2015_12_a73
S. A. Solovyev; S. Tordeux. An efficient truncated SVD of large matrices based on the low-rank approximation for inverse geophysical problems. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 12 (2015), pp. 592-609. http://geodesic.mathdoc.fr/item/SEMR_2015_12_a73/

[1] N. S. Bakhvalov, Numerical Methods, Nauka, 1973 (in Russian) | MR

[2] S. Chaillat, M. Bonnet, “Recent advances on the fast multipole accelerated boundary element method for 3D time-harmonic elastodynamics”, Wave Motion, 50:7 (2013), 1090–1104 | DOI | MR

[3] J. Demmel, W. Kahan, “Accurate singular values of bidiagonal matrices”, SIAM Journal on Scientific and Statistical Computing, 11:5 (1990), 873–912 | DOI | MR | Zbl

[4] Z. Drmac, K. Veselic, “New fast and accurate Jacobi SVD algorithm, I”, SIAM J. Matrix Anal. Appl., 35:2 (2008), 1322–1342 | DOI | MR | Zbl

[5] A. Gumerov, R. Duraiswami, Fast multipole methods for the Helmholtz equation in three dimensions, Elsevier, Amsterdam, 2004

[6] N. Halko, P. Martinsson, J. A. Tropp, “Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions”, SIAM Review, 53:2 (2011), 217–288 | DOI | MR | Zbl

[7] I. Silvestrov, D. Neklyudov, C. Kostov, V. Tcheverda, “Full-waveform inversion for macro velocity model reconstruction in look-ahead offset VSP: numerical SVD-based analysis”, Geophysical Prospecting, 61:6 (2013), 1099–1113 | DOI

[8] G. Ming, S. C. Eisenstat, “Efficient algorithms for computing a strong rank-revealing QR factorization”, SIAM Journal on Scientific Computing, 17:4 (1996), 848–869 | DOI | MR | Zbl

[9] J. M. Ortega, W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Acad. Press, New York, 1970 | MR | Zbl

[10] P. P. M. De Rijk, “A one-sided Jacobi algorithm for computing the singular value decomposition on a vector computer”, SIAM J. Sci. Stat. Comp., 10 (1998), 359–371 | DOI | MR

[11] S. Rjasanow, “Adaptive cross approximation of dense matrices”, IABEM 2002, International Association for Boundary Element Methods (UT Austin, TX, USA, May 28–30, 2002)

[12] O. Schenk, K. Gartner, “On fast factorization pivoting methods for sparse symmetric indefinite systems”, Electronic Transactions on Numerical Analysis, 23 (2006), 158–179 | MR | Zbl

[13] I. Silvestrov, D. Neklyudov, M. Puckett, V. Tcheverda, “Resolution and stability analysis of offset VSP acquisition scenarios with applications to full-waveform inversion”, SEG Technical Program Expanded Abstracts 2012, 2012

[14] W. Menke, Geophysical Data Analysis: Discrete Inverse Theory, Academic Press, Inc., New York, 1984 | MR