What is the amount of calculations needed to compute the $N$ lowest
eigenfunctions of a differential operator discretized on $N_g$ gridpoints?
Current numerical algorithms (including multigrid methods) require $O(N^2 N_g)$
operations, since each eigenfunction needs to be orthogonalized with respect
to each other.
This query arises in many important scientific problems, from image
segmentation to quantum-chemistry calculations of electronic structures. We
give special emphasis to the important example of computing the eigenfunctions
of the Schr\"odinger operator $-\Delta+V(x)$.
Our novel approach calculates, to accuracy $\varepsilon$, $N$ eigenfunctions of
a differential operator discretized on $N_g$ gridpoints in $O(N_g \log N
\log(1/\varepsilon))$ computer operations. This approach is based on the
observation that ``neighboring'' eigenfunctions are distinguishable from each
other only at large enough scales, and hence, in suitable representations, one
can use a common description of their details at finer scales, and
progressively separate them out only on increasingly coarser grids. Moreover,
the developed \emph{multiscale eigenbasis} (MEB) structure can be used to
expand a given function in terms of the $N$ eigenfunctions, again at the cost
of just $O(N_g \log N)$ operations.
The feasibility of obtaining the $O(N_g \log N)$ efficiency has first been
demonstrated for \emph{general 1D linear differential operators}. In
particular, our algorithms constitute a vast generalization of the
Fast Fourier Transform (FFT), whose basis functions are the eigenfunctions of
discretized differential operators with constant coefficients, periodic
boundary conditions with $2^l$ uniformly spaced gridpoints. The novel
$O(N \log N)$ expansion is in terms of the eigenfunctions of a general operator
with general boundary conditions and a general number and uniformity of
gridpoints.
Current research with Prof. Achi Brandt is concerned with the far-from-trivial
extension of these algorithms to higher dimensional problems. It is intimately
related to the extension of multigrid methods for wave equations to variable
coefficients.
Copyright. All Rights Reserved.