Analysis-Based Fast Numerical Algorithms of Applied Mathematics

One of the principal problems addressed by applied mathematics is the application of various linear operators (or rather, their discretizations) to more or less arbitrary vectors. As is well known, applying directly a dense (N x N)-matrix to a vector requires roughly N2 operations, and this simple fact is a cause of serious difficulties encountered in large-scale computations. For example, the main reason for the limited use of integral equations as a numerical tool in large-scale computations is that they normally lead to dense systems of linear algebraic equations, and the latter have to be solved, either directly or iteratively. Most iterative methods for the solution of systems of linear equations involve the application of the matrix of the system to a sequence of recursively generated vectors, which tends to be prohibitively expensive for large-scale problems. The situation is even worse if a direct solver for the linear system is used, as such solvers normally require O(N3) operations. As a result, in most areas of computational mathematics dense matrices are simply avoided whenever possible. For example, finite difference and finite element methods can be viewed as devices for reducing a partial differential equation to a sparse linear system. In this case, the cost of sparsity is the inherently high condition number of the resulting matrices.