Parallel Prony's method with multivariate matrix pencil approach and its numerical aspects (CROSBI ID 287476)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Bosner, Nela
engleski
Parallel Prony's method with multivariate matrix pencil approach and its numerical aspects
Prony's method is a standard tool exploited for solving many imaging and data analysis problems that result in parameter identification in sparse exponential sums $f(k)=\sum_{; ; ; j=1}; ; ; ^{; ; ; M}; ; ; c_{; ; ; j}; ; ; e^{; ; ; -2\pi i\langle t_{; ; ; j}; ; ; , k\rangle}; ; ; $, $k\in \mathbb{; ; ; Z}; ; ; ^{; ; ; d}; ; ; $, where the parameters are pairwise different $\{; ; ; t_{; ; ; j}; ; ; \}; ; ; _{; ; ; j=1}; ; ; ^{; ; ; M}; ; ; \subset [0, 1)^{; ; ; d}; ; ; $, and $\{; ; ; c_{; ; ; j}; ; ; \}; ; ; _{; ; ; j=1}; ; ; ^{; ; ; M}; ; ; \subset \mathbb{; ; ; C}; ; ; \setminus \{; ; ; 0\}; ; ; $ are nonzero. The focus of our investigation is on a Prony's method variant based on a multivariate matrix pencil approach. The method constructs matrices $S_{; ; ; 1}; ; ; $, łdots , $S_{; ; ; d}; ; ; $ from the sampling values, and their simultaneous diagonalization yields the parameters $\{; ; ; t_{; ; ; j}; ; ; \}; ; ; _{; ; ; j=1}; ; ; ^{; ; ; M}; ; ; $. The parameters $\{; ; ; c_{; ; ; j}; ; ; \}; ; ; _{; ; ; j=1}; ; ; ^{; ; ; M}; ; ; $ are computed as the solution of an linear least squares problem, where the matrix of the problem is determined by $\{; ; ; t_{; ; ; j}; ; ; \}; ; ; _{; ; ; j=1}; ; ; ^{; ; ; M}; ; ; $. Since the method involves independent generation and manipulation of a certain number of matrices, there is an intrinsic capacity for parallelization of the whole computational process on several levels. Hence, we propose a parallel version of the Prony's method in order to increase its efficiency. The tasks concerning the generation of matrices are divided among the block of threads of the graphics processing unit (GPU) and the central processing unit (CPU), where heavier load is put on the GPU. From the algorithmic point of view, the CPU is dedicated to the more complex tasks of computing the singular value decomposition, the eigendecomposition, and the solution of the least squares problem, while the GPU is performing matrix--matrix multiplications and summations. With careful choice of algorithms solving the subtasks, the load between CPU and GPU is balanced. Besides the parallelization techniques, we are also concerned with some numerical issues, and we provide detailed numerical analysis of the method in case of noisy input data. Finally, we performed a set of numerical tests which confirm superior efficiency of the parallel algorithm and consistency of the forward error with the results of numerical analysis.
Prony's method ; parallel algorithm ; efficient GPU-CPU implementation ; numerical analysis
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o izdanju
42 (2)
2021.
635-658
objavljeno
0895-4798
1095-7162
10.1137/20M1343658
Povezanost rada
Matematika, Računarstvo