Other projects:
The Multiscale method is a class of algorithmic techniques for solving efficiently and effectively large-scale computational and optimization problems. This method was originally invented for solving elliptic partial differential equations and up to now it represents the most effective class of numerical algorithms for them. During the last two decades, there were many successful attempts to adapt the multiscale method for combinatorial optimization problems. Whereas the variety of continuous systems' multiscale algorithms turned into a separate field of applied mathematics, for combinatorial optimization problems they still have not reached an advanced stage of development, consisting in practice of a very limited number of multiscale techniques.
The main objective of a multiscale algorithm is to create a hierarchy of problems (coarsening), each representing the original problem, but with fewer degrees of freedom. For the graph modeled problems, this hierarchy may be viewed as a process of learning of a graph topology prior to applying any approximation method. The construction of hierarchies at different scales ends up at the level with a very small number of degrees of freedom (coarsest level) that allows to get a first approximation to the original problem at very large scale within an insignificant running time (even for exact algorithm) in comparison to the size of original problem. Then, the obtained approximation is sequentially projected along all levels of the hierarchy (interpolation or projection) until it reaches the original problem with some approximation for it. The projection stage can be reinforced at each level by some refinement algorithm that improves the quality of approximation before further projection. The projection reinforced by a refinement method is called uncoarsening. Multiscale representation of a manifold on which a combinatorial optimization problem is formulated allows to apply different approximation or exact methods at all scales. Adapting these methods for working at local domains only can improve the overall complexity significantly while applying them at different scales implies the preservation of large-scale solution features inherited from coarser scales.
Multiscale frameworks is one of the focus areas of CSCAPES members.
Publications