Heirarchical Basis Multigrid/ILU Algorithms for Solving Finite Element Equations

9706090银行 分层基多重网格/ILU算法 求解有限元方程 兰多夫E.银行数学系 加州大学圣地亚哥分校 拉霍亚，CA 92093 这项建议有两个主要组成部分。首先，我们将研究代数层次基多重网格算法（HBMG/ILU）。 这些方法解决稀疏的线性方程组所产生的有限差分，有限体积和有限元离散偏微分方程。 它们与经典的HBMG和MG方法不同，因为它们不需要粗网格和网格细化序列。 这使得应用程序的几何复杂的域，需要许多元素的几何定义的问题，和自适应性来自移动网格点，而不是从细化的问题。 初步的数值实验表明，该方法是潜在的非常强大和强大的。建议的第二个组成部分涉及有限元程序PLTMG的持续软件开发。自20世纪70年代后期以来，该程序的各种版本已进入公共领域，并广泛用于教育和研究环境。 PLTMG解决标量，参数相关，非线性椭圆偏微分方程的一般区域的平面。 其主要特点是自适应网格生成，后验误差估计，HBMG（即将HBMG/ILU）迭代线性方程组，牛顿法的非线性，并继续参数依赖性。该代码还包括一个初始网格生成器、一个骨架生成器和几个图形例程。尽管PLTMG的名称保持不变，但通常每个新版本都会对软件包的80%或更多内容进行修改。 在许多由偏微分方程建模的系统中，临界现象仅发生在物理域的一小部分中，并且可能作为时间的函数（例如，作为火焰前缘）移动。即使在硬件方面有了很大的进步，使用基于简单均匀网格的软件来解决这种类型的困难的大挑战类问题是不够的;问题的需求要求将计算资源集中在最感兴趣的区域。 自适应网格算法的动机是算法本身可以并且应该识别这些关键区域，并在很少或没有人为干预的情况下用适当的网格进行响应。 自适应算法的“大脑”是一个后验误差指标，它既可以估计当前的误差，也可以指示应该集中额外资源的地方。自适应算法产生的非常不均匀和非结构化的网格需要复杂的方法，如多重网格或建议的HBMG/ILU，以有效和可靠地解决由此产生的方程组。总的来说，这个领域提供了一个马赛克的重要和相互关联的科学问题，从数学分析中的困难问题，以实现这些程序在现代计算机体系结构的困难的计算挑战。

9706090 Bank Hierarchical Basis Multigrid/ILU Algorithms for Solving Finite Element Equations Randolph E. Bank Department of Mathematics University of California at San Diego La Jolla, CA 92093 This proposal has two main components. First, we will study algebraic hierarchical basis multigrid algorithms (HBMG/ILU). These methods solve sparse sets of linear equations arising from finite difference, finite volume and finite element discretizations of partial differential equations. They are differentiated from classical HBMG and MG methods in that they do not require a coarse grid and sequence of mesh refinements. This allows application to problems with geometrically complex domains that require many elements just for the geometric definition, and problems where the adaptivity comes from moving the mesh points rather than from refinement. Preliminary numerical experiments indicate that the methods are potentially very powerful and robust. The second component of the of proposal concerns the continuing software development of the finite element program PLTMG. Various versions of this program have been in the public domain since the late 1970's, and it is widely used in education and research environments. PLTMG solves scalar, parameter dependent, nonlinear elliptic PDE's in general regions of the plane. The principle features are adaptive mesh generation, a posteriori error estimation, HBMG (soon to be HBMG/ILU) iteration for linear systems of equations, Newton's method for nonlinearities, and continuation for parameter dependencies. The code also includes an initial mesh generator, a skeleton generator, and several graphics routines. Although the name PLTMG has remained the same, typically 80% or more of the package is revised with each new release. In many systems modeled by partial differential equations, the critical phenomena occur only in a small part of the physical domain, and may move as a function of time ( e.g. as a flame front). Even with the great advances in hardware, it is not adequate to address difficult grand-challenge class problems of this type using software based on simple uniform meshes; the demands of the problem require that computing resources be focused on the regions of most interest. The motivation for adaptive mesh algorithms is that the algorithm itself can and should identify these critical regions and respond with an appropriate mesh with little or no human intervention. The ``brains'' of adaptive algorithms are a posterior error indicators, which both estimate the current error, and indicate where additional resources should be focused. The very nonuniform and unstructured meshes resulting from adaptive algorithms require sophisticated methods, such as multigrid or the proposed HBMG/ILU, to efficiently and reliably solve the resulting systems of equations. Overall, this field provides a mosaic of important and interrelated scientific questions ranging from difficult problems in mathematical analysis to difficult computational challenges in implementing these procedures on modern computer architectures.