III: CGV: Small: Designing an Adaptive Method for Solving Large Linear Systems of Equations in Two and Three-Dimensional Space

在许多工程和科学学科中，从图像处理到流体动力学模拟，系统的状态很容易用局部关系来描述(例如，在图像中的每个点，一个像素应该比它的邻居更亮/更暗)。将这些局部关系转换为全局值集(例如，为满足这些关系的每个像素分配亮度值)需要求解称为泊松系统的大型线性方程组。拟议研究的动机是，虽然线性系统是全球性的，空间中一点的性质会影响远处的解，但在许多情况下，只在特定位置需要解的细节(例如，当将多个图像合并成单个全景图时，只需要接缝附近的详细解)。结果，花费在估计这些感兴趣区域之外的解的细节上的计算努力被浪费了。利用这一观察结果，该项目旨在开发一种求解泊松系统的新方法--提供一种适应传统技术的方法，以便只将计算集中在需要的地方，从而将内存需求和运行时间减少数量级。这将对广泛的学科产生重大影响，使其能够在比目前可能的时间和内存更少的情况下找到满足当地关系的解决方案的所需部分。除了在计算科学中提供重大影响(在计算科学中，求解此类系统是许多模拟的标准部分)，这种方法还可能对科学教育产生影响，因为它可以实时模拟物理过程，使学生能够交互地探索不同物理变量的影响，从而丰富直观的理解。在适应的网格上实现泊松方程的多重网格解的关键观察是，在泊松系统中，远距离效应由较低的频率主导，因此解的高分辨率分量只需要在感兴趣的区域中计算。本项目研究的方法将利用这一观察结果，并扩展传统的多重网格，以便它可以在适应区域或兴趣的四叉树/八叉树上实施。这使得能够将由嵌入空间的维度确定的空间/时间复杂性替换为由期望精确解的流形的维度确定的空间/时间复杂性。为了实现这样的求解器，传统的多重网格方法将从两个方面进行修改。首先，为了补偿较粗的解不能向上采样到较细的分辨率的事实，线性系统的解将被表示为层次的所有级别上的函数的线性组合，而不仅仅是最细的一个。其次，求解器不是使用传统的限制和延长操作符在层次结构的连续级别之间转换，而是通过迭代层次结构的各个级别(如典型的V或W循环中那样，从精细到粗略，然后从粗略到精细)进行迭代，放松每个级别内的系统，并调整其他级别上的约束，考虑到已经满足的解决方案的组件。例如，在延长阶段，通过调整约束条件，将较粗略的解合并到较细的水平，而不是更新当前对解的估计。这项研究将探索这种系统的总体设计，以及与领域专家合作开发的特定领域的实现。由此产生的框架将促进在物理模拟、计算流体动力学、表面重建和图像处理领域的部署。在这些应用中，自由度数量的减少应该会导致效率提高约100倍，并且应该能够在商用PC上解决超大规模系统；而以前这些都被归类到高性能分布式计算的环境中。结果将以有文件记录的C/C++源代码的形式公布，用于构建适应的四叉树/八叉树，制定系统约束条件，并评估计算的解决方案。项目网站(http://www.cs.jhu.edu/~misha/Code/AdaptiveMG/)提供了进一步的信息和结果。

In numerous engineering and scientific disciplines, ranging from-image processing to simulation of fluid dynamics, the state of a system is easy to describe in terms of local relations (e.g., at each point in the image, a pixel should be brighter/darker than its neighbors). Transforming these local relations into a global set of values (e.g., assigning a brightness value to each pixel that satisfies these relations) requires solving a large system of linear equations, called the Poisson system. The proposed research is motivated by the observation that although the linear system is global, with properties at one point in space affecting the solution at points far away, in many cases the details of the solution are only required at particular locations (e.g., when merging multiple images into a single panorama, a detailed solution is only needed near the seams). As a result, computational effort expended on estimating the details of the solution away from these regions of interest is wasted. Using this observation, this project aims to develop a new method for solving the Poisson system -- providing a way to adapt traditional techniques so that computation is only focused where it is needed, reducing both the memory requirements and running times by orders of magnitude. This will have significant impact across a broad range of disciplines, making it possible to find the desired part of the solution that satisfies the local relations in less time and with less memory than is currently possible. In addition to providing significant impact in computational sciences (where solving such systems is a standard part of many simulations), such an approach could also have an impact on science education, as it can enable real-time simulation of physical processes, making it possible for students to interactively explore the effect of different physical variables, thereby enriching intuitive understanding.The key observation enabling a multigrid solution of the Poisson equation over an adapted grid is that, in a Poisson system, long-distance effects are dominated by lower frequencies, so high-resolution components of the solution need only be computed in regions of interest. The approach investigated in this project will leverage this observation and extend traditional multigrid so that it can be implemented over quadtrees/octree that are adapted to the regions or interest. This enables replacing a space/time complexity that is determined by the dimension of the embedding space with a space/time complexity that is determined by the dimension of the manifold over which an accurate solution is desired. To implement such a solver, the traditional multigrid approach will be modified in two ways. First, to compensate for the fact that the coarser solution cannot be up-sampled to the finer resolutions, the solution of the linear system will be represented as a linear combination of functions at all levels of the hierarchy, not just the finest one. Second, instead of using traditional restriction and prolongation operators to transition between successive levels of the hierarchy, the solver will proceed by iterating through the levels of the hierarchy (fine-to-coarse and then coarse-to-fine as in a typical V- or W-cycle), relaxing the system within each level, and adjusting the constraints at the other levels, accounting for the components of the solution that have already been met. For example, in the prolongation phase, the coarser solution will be incorporated into the finer levels by adjusting the constraints, rather than updating the current estimate of the solution. The research will explore the general design of such a system, as well as domain-specific implementations developed in collaboration with domain experts. The resulting framework will facilitate deployment in the areas of physical simulation, computational fluid dynamics, surface reconstruction, and image processing. In these applications, the reduction in the number of degrees of freedom should result in a ~100-fold increase in efficiency and should enable the solution of very large-scale systems on commodity PCs; whereas previously these were relegated to the context of high performance distributed computing. Results will be made publicly available in the form documented C/C++ source code for constructing adapted quadtrees/octrees, formulating the system constraints, and evaluating the computed solution. Project web site (http://www.cs.jhu.edu/~misha/Code/AdaptiveMG/) provides access to further information and results.