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.

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