Эффективность параллельной реализации алгоритма Radix-4 быстрого преобразования Фурье
Parallel program for the fast Fourier transform is implemented on the basis of MPI (Message Passing Interface) technology. Radix-4 algorithm is chosen as a basic method to use. The dependence of parallel calculation acceleration on the number of processors is studied for two supercomputers. The formula describing the dependence of the calculation time on the number of processors is proposed for the range of the input data volume and supercomputer characteristics. The number of nodes providing you with maximum acceleration of calculation is estimated.
This paper deals with the technique known as the periodic synchronous averaging. The exact analytical expression for the fast Fourier transform (FFT) representing the digital spectrum of the signal undergoing periodic synchronous averaging is derived using the general signal and spectral framework. This formula connects the coefficient of Fourier series of the original continuous-time signal with the FFT of the averaged sampled version taking into consideration all the effects such as difference between the true and averaging periods, the attenuation and the leakage. The results of the numerical simulation are presented for the case of periodic signal, which was chosen a train of triangle pulses, the spectrum of which possesses a closed form and whose Fourier series coefficients rapidly decrease with the index. The chosen example allows the authors to illustrate that the waveform of the recovered signal can vary significantly, despite a rather slight difference in values between the true and averaging periods. Another important effect emphasized in the presented paper is that overall distinction between the original and averaged signals measured by means of relative mean square error raises if the total observation length increases while the other parameters remain fixed.
We present direct logarithmically optimal in theory and fast in practice algorithms to implement the tensor products finite element method (FEM) based on the tensor products of the 1D high-order FEM spaces on multi-dimensional rectangular parallelepipeds for solving the $N$-dimensional Poisson type equation $-\Delta u+\alpha u=f$ ($N\geq 2$) with the Dirichlet boundary conditions. They are based on the well-known Fourier approaches. The key new points are a detailed description for the eigenpairs of the 1D eigenvalue problems for the high order FEM as well as the fast direct and inverse algorithms for expansion in the respective eigenvectors utilizing simultaneously several versions of the FFT (fast Fourier transform). Results of numerical experiments in 2D and 3D cases are presented. The algorithms can serve for numerous applications, in particular, to implement the tensor product high order finite element methods for various time-dependent partial differential equations (PDEs) including the multidimensional heat, wave and Schrödinger ones. %
Modern Elbrus-4S and Elbrus-8S processors show floating point performance comparable to the popular Intel processors in the field of high-performance computing. Tasks oriented to take advantage of the VLIW architecture show even greater efficiency on Elbrus processors. In this paper the efficiency of the most popular materials science codes in the field of classical molecular dynamics and quantum-mechanical calculations is considered. A comparative analysis of the performance of these codes on Elbrus processor and other modern processors is carried out
A new fast direct algorithm for implementing a finite element method (FEM) of order on rectangles as applied to boundary value problems for Poisson-type equations is described that extends a well-known algorithm for the case of difference schemes or bilinear finite elements (n = 1). Its core consists of fast direct and inverse algorithms for expansion in terms of eigenvectors of one-dimensional eigenvalue problems for an nth-order FEM based on the fast discrete Fourier transform. The amount of arithmetic operations is logarithmically optimal in the theory and is rather attractive in practice. The algorithm admits numerous further applications (including the multidimensional case).
We consider certain spaces of functions on the circle, which naturally appear in harmonic analysis, and superposition operators on these spaces. We study the following question: which functions have the property that each their superposition with a homeomorphism of the circle belongs to a given space? We also study the multidimensional case.
We consider the spaces of functions on the m-dimensional torus, whose Fourier transform is p -summable. We obtain estimates for the norms of the exponential functions deformed by a C1 -smooth phase. The results generalize to the multidimensional case the one-dimensional results obtained by the author earlier in “Quantitative estimates in the Beurling—Helson theorem”, Sbornik: Mathematics, 201:12 (2010), 1811 – 1836.
We consider the spaces of function on the circle whose Fourier transform is p-summable. We obtain estimates for the norms of exponential functions deformed by a C1 -smooth phase.