Geodesic
A parallel implementation of the matrix cross approximation method
Numerical methods and programming, Tome 16 (2015) no. 3, pp. 369-375.

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

The matrix cross approximation method is a fast method based on low-rank matrix approximations with complexity $O((m+n)r^2)$ arithmetic operations. Its main feature consists in the following: if a matrix is not given as an array but is given as a function of two integer arguments, then this method allows one to compute the low-rank approximation of the given matrix by evaluating only $O((m+n)r)$ values of this function. However, if the matrix is extremely large or the evaluation of its elements is computationally expensive, then such an approximation becomes timeconsuming. For such cases, the performance of the method can be improved via parallelization. In this paper we propose an efficient parallel algorithm for the case of an equal computational cost for the evaluation of each matrix element.
Keywords: low-rank matrix approximations, matrix cross approximation method, parallel algorithms. 
@article{VMP_2015_16_3_a4,
     author = {D. A. Zheltkov and E. E. Tyrtyshnikov},
     title = {A parallel implementation of the matrix cross approximation method},
     journal = {Numerical methods and programming},
     pages = {369--375},
     publisher = {mathdoc},
     volume = {16},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMP_2015_16_3_a4/}
}
TY  - JOUR
AU  - D. A. Zheltkov
AU  - E. E. Tyrtyshnikov
TI  - A parallel implementation of the matrix cross approximation method
JO  - Numerical methods and programming
PY  - 2015
SP  - 369
EP  - 375
VL  - 16
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VMP_2015_16_3_a4/
LA  - ru
ID  - VMP_2015_16_3_a4
ER  - 
%0 Journal Article
%A D. A. Zheltkov
%A E. E. Tyrtyshnikov
%T A parallel implementation of the matrix cross approximation method
%J Numerical methods and programming
%D 2015
%P 369-375
%V 16
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VMP_2015_16_3_a4/
%G ru
%F VMP_2015_16_3_a4
D. A. Zheltkov; E. E. Tyrtyshnikov. A parallel implementation of the matrix cross approximation method. Numerical methods and programming, Tome 16 (2015) no. 3, pp. 369-375. http://geodesic.mathdoc.fr/item/VMP_2015_16_3_a4/