Most of the fundamental problems in physics, chemistryand engineering involve computation too hard even for future supercomputers, if conventional mathematical approaches are used. The reason is always a product of several complexity factors associated with the wide range of space and time scales characteristic to such problems. Each of these complexity factors can in principle be removed by various multiscale algorithms, i.e., employing separate processing at each scale of the problem, combined with interscale iterative interactions. A wide range of multiscale computational methods is described, emphasizing main ideas and interrelations between various fields. The reported areas include: top-efflciency multigrid methods in fluid dynamics; inverse PDE problems and data assimilation; feedback optimal control; PDE solvers on unbounded domains and on adaptable grids; wave/ray methods for highly indefinite equations; rigorous quantitative analysis of multigrid; many-eigenfunction problems and ab-initio quantum chemistry; fast evaluation of integral transforms on adaptive grids; multigrid Dirac solvers; fast inverse-matrix and determinant calculations and updates; multiscale Monte-Carlo methods in statistical physics, including the renormalization multigrid (RMG) methods; molecular mechanics (including fast force summation, fast macromolecular energy minimization, and Monte-Carlo methods at equilibrium, both for macromolecules and for large ensembles of small molecules); combination of small-scale equilibrium with large-scale dynamics; image processing (edge detection and picture segmentation); tomography (medical imaging and radar reconstruction); efflcient, general and highly accurate algebraic multigrid (AMG) schemes; fast practical graph algorithms; data clustering; and multiscale approaches to global optimization.
Research supported by AFOSR and the Materials and Manufacturing Directorate, AFRL, Wright-Patterson Base, contract No. F33615-97-D-5405, by the European Offlce of Aerospace Research and Development (EOARD) of the US Air Force, Contract F61775-00-WE067, by Israel Ministry of Science, Cultureand Sport grant 9680, by Israel Absorption Ministry, Project No. 6682, by Israel Science Foundation grant No. 696/97, and by the Carl F. Gauss Minerva Center for Scientific Computation at the Weizmann Institute of Science.