Andrew V. Terekhov

Andrew V. Terekhov

In this study, we develop a new parallel algorithm for solving systems of linear algebraic equations with the same block-tridiagonal matrix but with different right-hand sides. The method is a generalization of the parallel dichotomy algorithm for solving systems of linear equations with tridiagonal matrices \cite{terekhov:Dichotomy}. Using this approach, we propose a parallel realization of the domain decomposition method (\mbox{the Schur} complement method). The calculation of acoustic wave fields using the spectral-difference technique improves the efficiency of the parallel algorithms. A near-linear dependence of the speedup with the number of processors is attained using both several and several thousands of processors. This study is innovative because the parallel algorithm developed for solving block-tridiagonal systems of equations is an effective and simple set of procedures for solving engineering tasks on a supercomputer.

Alexey G. Fatyanov, Andrew V. Terekhov

A high-performance parallel algorithm is proposed for modeling the propagation of acoustic and elastic waves in inhomogeneous media. An initial boundary-value problem is replaced by a series of boundary-value problems for a constant elliptic operator and different right-hand sides via the integral Laguerre transform. It is proposed to solve difference equations by the conjugate gradient method for acoustic equations and by the GMRES$(k)$ method for modeling elastic waves. A preconditioning operator was the Laplace operator that is inverted using the variable separation method. The novelty of the proposed algorithm is using the Dichotomy Algorithm (Terekhov, 2010), which was designed for solving a series of tridiagonal systems of linear equations, in the context of the preconditioning operator inversion. Via considering analytical solutions, it is shown that modeling wave processes for long instants of time requires high-resolution meshes. The proposed parallel fine-mesh algorithm enabled to solve real application seismic problems in acceptable time and with high accuracy. By solving model problems, it is demonstrated that the considered parallel algorithm possesses high performance and efficiency over a wide range of the number of processors (from 2 to 8192).

Andrew V. Terekhov

This paper presents a new finite difference algorithm for solving the 2D one-way wave equation with a preliminary approximation of a pseudo-differential operator by a system of partial differential equations. As opposed to the existing approaches, the integral Laguerre transform instead of Fourier transform is used. After carrying out the approximation of spatial variables it is possible to obtain systems of linear algebraic equations with better computing properties and to reduce computer costs for their solution. High accuracy of calculations is attained at the expense of employing finite difference approximations of higher accuracy order that are based on the dispersion-relationship-preserving method and the Richardson extrapolation in the downward continuation direction. The numerical experiments have verified that as compared to the spectral difference method based on Fourier transform, the new algorithm allows one to calculate wave fields with a higher degree of accuracy and a lower level of numerical noise and artifacts including those for non-smooth velocity models. In the context of solving the geophysical problem the post-stack migration for velocity models of the types Syncline and Sigsbee2A has been carried out. It is shown that the images obtained contain lesser noise and are considerably better focused as compared to those obtained by the known Fourier Finite Difference and Phase-Shift Plus Interpolation methods. There is an opinion that purely finite difference approaches do not allow carrying out the seismic migration procedure with sufficient accuracy, however the results obtained disprove this statement. For the supercomputer implementation it is proposed to use the parallel dichotomy algorithm when solving systems of linear algebraic equations with block-tridiagonal matrices.

Andrew V. Terekhov

This paper considers spectral-difference methods of a high-order of accuracy for solving the one-way wave equation using the Laguerre integral transform with respect to time as the base. In order to provide a high spatial accuracy and calculation stability, the Richardson method can be employed. However such an approach requires high computer costs, therefore we consider alternative algorithms based on the Adams multistep schemes. To reach the stability first for the 1D one-way equation and then for the 2D case, the stabilizing procedures using the spline interpolation were developed. This made possible to efficiently implement a predictor-corrector type method in terms of which a boundary value problem for high-order elliptic equations is substituted for a sequence of inversions of second order elliptic operators thus decreasing computer costs. To assess the accuracy and stability of difference approximations for the 1D one-way wave equation, the analytical solution based on the double Laguerre transform was obtained. This solution can be efficiently calculated if for summation one makes use of fast algorithms of computing a discrete linear convolution. For the 2D one-way wave equation the stability and accuracy of the procedures proposed have been studied on implementing the migration algorithm within a problem of seismic prospecting.

Andrew V. Terekhov

Basing on a modification of the "Dichotomy Algorithm" (Terekhov, 2010), we propose a parallel procedure for solving tridiagonal systems of equations with Toeplitz matrices. Taking the structure of the Toeplitz matrices, we may substantially reduce the number of the "preliminary calculations" of the Dichotomy Algorithm, which makes it possible to effectively solve a series as well as a single system of equations. On the example of solving of elliptic equations by the Separation Variable Method, we show that the computation accuracy is comparable with the sequential version of the Thomas method, and the dependence of the speedup on the number of processors is almost linear. The proposed modification is aimed at parallel realization of a broad class of numerical methods including the inversion of Toeplitz and quasi-Toeplitz tridiagonal matrices.

Andrew V. Terekhov

A parallel algorithm for computing the finite difference solution to the elliptic equations with non-separable variables is presented. The resultant matrix is symmetric positive definite, thus the preconditioning conjugate gradient or the chebyshev method can be applied. A differential analog to the Laplace operator is used as preconditioner. For inversion of the Laplace operator we implement a parallel version of the separation variable method, which includes the sequential FFT algorithm and the parallel solver for tridiagonal matrix equations (dichotomy algorithm). On an example of solving acoustic equations by the integral Laguerre transformation method, we show that the algorithm proposed is highly efficient for a large number of processors.