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.