Numerical Algorithms as Dynamcal Systems - Structure Preservation, Convergence Theory, and Rediscretization

作为动态系统的数值算法 - 结构保持、收敛理论和重新离散化

• 批准号: 1316779
• 负责人: Moody Chu
• 金额: $ 25万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-15 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1316779&HistoricalAwards=false
• 关键词: Numerical; Algorithms; Dynamcal; Systems; Structure

The focus of the project is to improve iterative algorithms in numerical analysis by linking them to particular systems of differential equations. Thirty years ago, it was realized that the QR algorithm for calculating eigenvalues can be considered as a time-T map of the Toda lattice. This opens up the possibility of bringing the qualitative methods of dynamical systems to bear on the algorithm, and to potentially speed up the algorithm by more efficient discretizations. The crucial aspect of the Toda lattice is that it is a continuous conjugation that preserves upper Hessenberg form and therefore the eigenvalues. In recent research, the PI has achieved similar results with the calculation of the singular value decomposition by developing a Lotka-Volterra system that preserves bidiagonal structures, which has led to advances in computing the SVD. This project investigates other dynamical systems preserving symplectic and Hamiltonian structure, which are pivotal in many areas of applications. The ultimate goal is to investigate the connection between their geometric structures and existing numerical algorithms, to establish a rigorous mathematical theory on dynamical behaviors, and to develop possible structure-preserving re-discretizations to improve robustness, speed, and accuracy of iterations in numerical analysis. Structure-preserving dynamical systems are natural and ubiquitous. Conservation laws in the physical world and constrained mechanics in engineered systems are just two examples. Structure preservation is also imperative in computation because it makes possible more efficient algorithms, improves physical feasibility and interpretability, and is more robust in long-term behavior. The proposed research recasts numerical algorithms as differential systems that mimic the structure-preserving properties of the corresponding iterative schemes. Understanding the overall dynamics of the continuum system can shed light on the convergence properties of the related discrete counterparts, and can also contribute to the re-discretization of the continuum system into a new algorithm with better numerical properties. A wide range of applications stands to benefit from the study of properties and geometric structure of these systems, which essentially include all disciplines that entail structure preservation, including classical and quantum mechanics, model reduction, reversible systems, and molecular dynamics.

该项目的重点是通过将数值分析中的迭代算法与特定的微分方程系统联系起来来改进它们。30年前，人们认识到计算本征值的QR算法可以被认为是户田格的时间-T映射。这开辟了将动力系统的定性方法应用于算法的可能性，并可能通过更有效的离散化来加速算法。户田格的关键方面是，它是一个连续的共轭，保持上海森伯形式，因此，本征值。在最近的研究中，PI通过开发保持双对角结构的Lotka-Volterra系统，实现了奇异值分解计算的类似结果，这导致了SVD计算的进步。本计画研究其他保辛与保哈密尔顿结构的动力系统，这些系统在许多应用领域都是关键的。最终目标是研究它们的几何结构和现有的数值算法之间的联系，建立一个严格的数学理论的动力学行为，并开发可能的结构保持重新离散化，以提高鲁棒性，速度和精度的迭代数值分析。结构保持动力系统是自然的和普遍存在的。物理世界中的守恒定律和工程系统中的约束力学只是两个例子。结构保持在计算中也是必不可少的，因为它使更有效的算法成为可能，提高了物理可行性和可解释性，并且在长期行为中更鲁棒。拟议的研究重铸数值算法作为微分系统，模仿相应的迭代方案的结构保持性能。理解连续系统的整体动力学可以揭示相关离散对应物的收敛性质，并且还可以有助于将连续系统重新离散为具有更好数值性质的新算法。广泛的应用将受益于这些系统的性质和几何结构的研究，基本上包括所有需要结构保持的学科，包括经典和量子力学，模型简化，可逆系统和分子动力学。