Sparse Direct Solvers for Unassembled Hyper-Matrices

未组装超矩阵的稀疏直接求解器

• 批准号: 0625917
• 负责人: Victor Eijkhout
• 金额: $ 39.67万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0625917&HistoricalAwards=false
• 关键词: Sparse; Direct; Solvers; Unassembled; Hyper

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.

目前可用的稀疏直接求解器背后的基本假设，即单独解决隔离应该takemintime，并不代表在自适应有限元方法的设置中的最佳解决方案。 在那里，当局部细化发生时，可以更新来自当前细化的解的因式分解形式的中间结果。 该项目的两个创新之处在于：一个接口，允许应用程序将有关细化的信息传递到直接求解器库和一个数据结构，Unassembled HyperMatrix，它允许稀疏矩阵及其分解以未组装的格式存储，便于矩阵及其分解的更新。 换句话说，这项研究是基于这样的思想，即从域的精化历史中继承消去树，并存储在所有级别上未组装的元素矩阵，仅在必要时组装它们以进行因子分解。由于最终的求解器在元素矩阵方面完全发挥作用，因此稠密子矩阵自然地暴露为因子分解的一部分，这将允许像3级BLAS这样的高性能内核得到充分利用。研究的重点包括设计一个API，以最佳方式将求解器集成到应用程序中，开发UncertaintedHyperMatrix基础设施，以及研究稳定性和复杂性，特别是不确定情况下的主元策略的设计，计算模拟已经成为科学中两种传统方法--理论和实验的平等伙伴。 在许多应用中，从汽车振动的模拟到雷达上飞机的雷达特征信号的计算，有限元法是首选的计算方法。这些方法中最好的方法是使用自适应近似来平衡精度和求解所需的时间。 当然，大多数时间都花在解线性方程组上。 这是减少这种解决方案的时间，在一个自适应应用程序的特定设置，这是本研究的重点。 创新是这个项目的基础consists在存储的线性系统在一个新的格式，UnqualledHyperMatrix，这使得许多过去的计算被重用时，一个适应发生。 与这一理论创新携手并进的是一个接口的开发，该接口允许应用程序表达对求解器库的适应。 这种新方法有可能大大降低与适应相关的解决方案的成本。