engleski

Parallel Prony’s Method With Multivariate Matrix Pencil Approach

Prony's method is a standard tool for parameter identification in sparse exponential sums $$f(k)=\sum_{; ; ; j=1}; ; ; ^{; ; ; T}; ; ; c_{; ; ; j}; ; ; e^{; ; ; -2\pi i\langle t_{; ; ; j}; ; ; , k\rangle}; ; ; , \quad k\in \mathbb{; ; ; Z}; ; ; ^{; ; ; d}; ; ; , $$ where the parameters are pairwise different $\{; ; ; t_{; ; ; j}; ; ; \}; ; ; _{; ; ; j=1}; ; ; ^{; ; ; M}; ; ; \subset [0, 1)^{; ; ; d}; ; ; $, and nonzero $\{; ; ; c_{; ; ; j}; ; ; \}; ; ; _{; ; ; j=1}; ; ; ^{; ; ; M}; ; ; \subset \mathbb{; ; ; C}; ; ; \setminus \{; ; ; 0\}; ; ; $. The focus of our investigation is on a Prony's method variant based on a multivariate matrix pencil method \cite{; ; ; ekpr_rmmpm}; ; ; . The method constructs matrices $S_{; ; ; 1}; ; ; $, \ldots , $S_{; ; ; d}; ; ; $ from the sampling values, and their simultaneous diagonalization yields the parameters $\{; ; ; t_{; ; ; j}; ; ; \}; ; ; _{; ; ; j=1}; ; ; ^{; ; ; M}; ; ; $. The joint eigenbasis is obtained from the eigendecomposition of a single matrix that is random linear combination of $S_{; ; ; 1}; ; ; $, \ldots , $S_{; ; ; d}; ; ; $. 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 from $\{; ; ; t_{; ; ; j}; ; ; \}; ; ; _{; ; ; j=1}; ; ; ^{; ; ; M}; ; ; $. Since the method involves independent generation and manipulation of certain number of matrices, there is intrinsic capacity for parallelization of the whole computation process on several levels. On the first level, the tasks concerning generation of matrices is divided among GPU's block of threads and CPU, where heavier load is put on the GPU. On the second level, the individual threads are dealing with individual matrix elements. From the algorithmic point of view, the CPU is dedicated to the more complex tasks of computing SVD, eigendecomposition, and solution of the least squares problem, while the GPU is performing matrix--matrix multiplications and summations. With careful choice of the algorithms solving the subtask, the load between CPU and GPU can be balanced. Besides the parallelization techniques, we are also concerned with some numerical issues, and we will provide some numerical analysis results of the method.

Prony's method ; parallel algorithm ; efficient GPU-CPU implementation ; numerical analysis

nije evidentirano