Using Fourier and hartley transform for fast, approximate solution of dense linear systems

摘要

The solution of linear system of equations is one of the most common tasks in scientific computing. For a large dense systems that requires prohibitive number of operations of the order of magnitude n3, where n is the number of equations and also unknowns. We developed a novel numerical approach for finding an approximate solution of this problem based on Fourier or Hartley transform although any unitary, orthogonal transform which concentrates power in a small number of coefficients can be used. This is the strategy borrowed from digital signal processing where pruning off redundant information from spectra or filtering of selected information in frequency domain is the usual practice. The procedure is to transform the linear system along the columns and rows to the frequency domain, generating a transformed system. The least significant portions in the transformed system are deleted as the whole columns and rows, yielding a smaller, pruned system. The pruned system is solved in transform domain, yielding the approximate solution. The quality of approximate solution is compared against full system solution. Theoretical evaluation of the method relates the quality of approximation to the perturbation of eigenvalues of the residual matrix. Numerical experiments illustrating feasibility of the method and quality of the approximation, together with operations count are presented.