Font Size: a A A

The Research Of High Performance Preprocessing Techniques And Distributed Parallel Algorithm For Toeplitz Systems

Posted on:2005-08-29Degree:DoctorType:Dissertation
Country:ChinaCandidate:R H DanFull Text:PDF
GTID:1118360152457214Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
Toeplitz systems have been applied comprehensively in science and engineering. Many problems' solving, such as the filter coefficients in the design of recursive digital filters, the RCS of dipole-array antennas, the unknown parameters of stationary auto-regressives models in time series analysis, and minimum realization problems in control theory, all involves the solving of Toeplitz systems.Algorithms for solving Toeplitz systems fall into the categories of the preconditioned conjugate gradient method or multi-grid methods. The key point of the preconditioned conjugate gradient method is selecting a proper preconditioner, while the choice of the prolongation operator or the restriction operator has great effect on the convergence speed of the multi-grid methods. As a result, the research of preprocessing technique for Toeplitz systems, that is the choice of the preconditioners and the prolongation operator or the restriction operator, has been a hot topic of the Toeplitz solving in recent years.Today the distributed-memory multicomputer have become the computing environment for many scientific and engineering applications, and the preferred tools for solving grand challenge problems. So it is of great significance in theory and practice to study and design the high performance parallel algorithms for solving the Toeplitz systems under distributed-memory environments.Based on the above considerations, this thesis makes the following contributions:1. Extend the preconditioners' construction space. A new across-diagonalized preconditioner space based on Sine transform is proposed, and it is proved that the existing diagonalized preconditioner space based on Sine transform is its sub-space. In the sense ofminimizing P-T , the construct processes of the optimal across-diagonalized preconditionerP in the new space are presented. Compared with the diagonalized preconditioners, the new ones' construction doesn't increase the computation complexity. The numerical experiments on the high performance processors show that the eigenvalue property of the new ones is much better. When applied to the solving of the specified Toeplitz equations, the new preconditioners are proved efficient.2. A new idea via wavelet transform and the multi-grid methods is presented in order tosolve the ill-conditioned Toeplitz systems. After exposing the relation between restriction operators or prolongation operators in the multi-grid methods and low-pass filter or high-pass filter in wavelet transform, a new advanced structure of the biorthogonal compactly supported wavelet is put forward, especially, as an example a biorthogonal compactly supported 9/11 wavelet with advanced structure is constructed. Thus the new restriction operators and prolongation operators are proposed. The experiment results show that the new algorithm is efficient to solve the ill-conditioned Toeplitz equations.3. For tridiagnal Toeplitz systems, two parallel algorithms are presents. One is based on the complete LU decomposition of the coefficient matrices, the other is based on its near LU decomposition. By making use of the special structure of the coefficient matrices and 'Qingjiushao'algorithm, redundant computation is avoided and perfect parallelism is achieved. The theory analysis and numerical experiments on distributed-memory multi-computers showthat the two algorithms'speedups satisfy: . This is the ideal result for parallelalgorithms.4. A new algorithm for solving near tridiagnal Toeplitz systems is presented, with corresponding high performance parallel algorithm on distributed-memory multicomputers. The new parallel algorithm makes full use of the special structure of the coefficient matrix and avoidsredundant computation. Its absolute speedup satisfies: . That is also the idealresult that a parallel algorithm can reach.5. For the application of the parallel algorithms with preprocessing technique in signal processing, the following two studies are accomplished:(1) For the reconstruction of the non-uniform sampling signal, this thesis p...
Keywords/Search Tags:Toeplitz system, preconditioned conjugate gradient method, preconditioner, Sine transform, multi-grid method, wavelet transform, parallel algorithm, signal reconstruction
PDF Full Text Request
Related items