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晶格的Time-T映射。这打开了将动态系统定性方法置于算法上的可能性，并有可能通过更有效的离散化加速算法。 Toda晶格的关键方面是，它是一种连续的结合，可保留上赫森伯格上部形式，因此是特征值。在最近的研究中，PI通过开发保留BidiaGonal结构的Lotka-Volterra系统来计算单数值分解，从而取得了相似的结果，这导致了计算SVD的进步。该项目调查了保留符号和哈密顿结构的其他动力学系统，这些结构在许多应用领域都至关重要。最终目标是研究其几何结构与现有的数值算法之间的联系，以建立有关动力学行为的严格数学理论，并开发出可能的结构可扩展性的重新散发，以提高数值分析中迭代的稳健性，速度和准确性。具有结构的动力学系统是自然而无处不在的。物理世界中的保护定律和工程系统中的受限力学只是两个例子。在计算中，结构保存也必须进行，因为它使得可能更有效的算法，提高物理可行性和解释性，并且在长期行为上更健壮。拟议的研究将数值算法重现为模仿相应迭代方案结构赋予性能的差分系统。了解连续体系统的整体动力学可以阐明相关离散对应物的收敛属性，还可以有助于将连续体系统重新降级为具有更好数值属性的新算法。广泛的应用将受益于这些系统的性质和几何结构的研究，这些应用程序本质上包括所有需要保存结构的学科，包括经典和量子力学，模型还原，可逆系统和分子动力学。