Sparse Direct Solvers for Unassembled Hyper-Matrices

目前可用的稀疏直接求解器背后的基本假设，即单独求解应该花费最少的时间，在自适应有限元方法的背景下并不代表最优解。在那里，当局部精化发生时，可以更新来自当前精化解的因式分解形式的中间结果。该项目的两项创新是：一个接口，允许应用程序将有关优化的信息传递给直接求解器库，以及一个数据结构，即未汇编的超级矩阵，它允许稀疏矩阵及其因式分解以一种非汇编格式存储，以促进矩阵及其因式分解的更新。换言之，本研究是基于继承领域精化历史中的消除树的思想，并存储在各个层次上拆卸的元素矩阵，只有在需要进行因式分解时才对其进行组装。由于所得到的求解器完全以元素矩阵的形式发挥作用，稠密的子矩阵自然被暴露为因式分解的一部分，这将使像Level-3 BLAS这样的高性能内核得到充分利用。研究的重点包括设计一个将求解器优化地集成到应用程序中的API，开发未汇编的超矩阵基础设施，以及对稳定性和复杂性的调查，特别是针对不确定情况的旋转策略的设计。计算模拟在科学、理论和实验两个传统方法中作为平等的伙伴而结合在一起。对于许多应用，从汽车振动的模拟到雷达上飞机雷达信号的计算，有限元方法是可选择的计算方法。这些方法中最好的是使用自适应近似来平衡精度和求解所需的时间。一成不变，大多数时间都花在解线性方程组上。在特定的自适应应用环境下，如何减少这种求解时间，是本文研究的重点。作为该项目基础的创新在于以一种新的格式存储线性系统，即未汇编的超级矩阵，该格式允许在发生适应时重复使用过去的大部分计算。与这一理论创新齐头并进的是接口的开发，该接口允许应用程序表达对求解器库的适应。新方法有可能大幅降低与适应相关的解决方案的成本。

The underlying assumption behind currently available sparse directsolvers, namely that an individual solve in isolation should takeminimal time, does not represent an optimal solution in the setting ofan adaptive finite element method. There, intermediate results, inthe form of a factorization, from the solution of a current refinementcan be updated when a local refinement occurs. Two innovationsunderlie the project: an interface that allows applications to passinformation about refinement to the direct solver library and a datastructure, the Unassembled HyperMatrix, that allows sparse matricesand their factorization to be stored in an unassembled format thatfacilitates the updating of the matrix and its factorization. Inother words, this research is based on the ideas of inheriting theelimination tree from the refinement history of the domain and storingelement matrices unassembled on all levels, assembling them only whennecessary for the factorization. Since the resulting solver functionsfully in terms of element matrices, dense submatrices are naturallyexposed as part of the factorization which will allow high-performancekernels like the level-3 BLAS to be fully exploited.The focus of the research includes the design of an API that optimally integrates thesolver into applications, the development of the UnassembledHyperMatrix infrastructure, and an investigation of stability andcomplexity, in particular the design of pivoting strategies for theindefinite case.Computational simulation has joined the two traditional methods inscience, theory and experiment, as an equal partner. For manyapplications, ranging from the similation of vibration in anautomobile to the computation of the radar signature an airplane onradar, finite element methods are the computational method of choice.The best of these methods use adaptive approximations to balanceaccuracy against the time required for the solution. Invariably, mosttime is spent in the solution of a system of linear equations. It isthe reduction of this solution time, in the specific setting of anadaptive application, that is the focus of thisresearch. The innovation that is the basis of this project consistsin storing the linear system in a new format, the UnassembledHyperMatrix, that allows much of a past computation to be reused whenan adaptation occurs. Hand in hand with this theoretical innovationgoes the development of an interface that allows an application toexpress adaptation to the solver library. The new approach has thepotential for reducing the cost of a solution related to an adaptationsubstantially.