Computing with Sparse and Structured Matrices: Mathematical Derivatives and Beyond

这项研究主要是为数学导数的计算或估计以及相关的科学计算问题设计有效的计算方法。我们的方法是基于组合学、图论和数值线性代数的协同作用来解决计算问题，其中问题的规模要求算法设计及其计算机实现的创新策略。我们研究方法的一个重要组成部分是识别和利用信息，如结构、稀疏性和并发性。 从计算金融到气象学再到电网，建模和解决不同应用领域出现的科学问题都有一个共同的主题：对稀疏或结构化的矩阵进行数值计算，或者两者兼而有之。麻省理工学院的大气环流模式MITgCM(研究地球气候的数值模式)是所谓的“亿级”应用的一个例子，在这种应用中，即使底层模式的一次模拟运行也需要史无前例的计算资源。在这样的数值模式中，一个基本的计算是关于模型对一些未知或未知的模型参数的灵敏度的评估。近年来在算法微分(AD)技术方面的出色研究使科学家能够“自动”计算MITgcm计算机代码的灵敏度。利用信息，如稀疏性和潜在问题的结构，在为此类应用设计有效的算法时至关重要。此外，现代高性能计算系统不断发展的体系结构复杂性对创新算法的有效软件实现提出了相当大的挑战。 更广泛地说，这项研究的结果有望在科学和工程计算中得到应用，这些计算涉及求解非线性方程组或某些量的优化(最小化或最大化)。这项研究的培训部分(研究生/本科培训)将为加拿大的高素质人才库(HQP)做出更大贡献。过去获得发现资助的所有受训人员都继续(或正在考虑)攻读研究生课程(理科硕士)。或博士水平)或积极为加拿大工业做出贡献(例如，辛克鲁德大学、Telus大学、莱斯布里奇大学)。

This research is mainly concerned with the design of efficient computational methods for the computation or estimation of mathematical derivatives and related scientific computing problems. Our approach is based on the synergy of combinatorics, graph theory, and numerical linear algebra to solve computational problems where the scale of the problem calls for innovative strategies for algorithm design and their computer implementation. An important component of our research methodology is the identification and exploitation of information such as structure, sparsity, and concurrency. Modelling and solving scientific problems arising in diverse application areas – from computational finance to meteorology to electricity grids, share a common theme: numerical calculations on matrices that are sparse or structured or both. The MIT general circulation model, MITgcm (a numerical model to study Earth’s climate), is an example of the so called “exascale” application where, even one simulation run of the underlying model requires computational resources of an unprecedented scale. An essential calculation in such a numerical model is concerned with the evaluation of sensitivity of the model with respect to some model parameters that are unknown or poorly known. Excellent research in algorithmic differentiation (AD) techniques in the recent years enabled scientists to “automate” sensitivity calculation for MITgcm computer code. Exploiting information such as sparsity and structure of the underlying problem is crucial in designing effective algorithms for such applications. Moreover, the evolving architectural complexity of modern high-performance computing systems pose considerable challenge for effective software implementation of innovative algorithms. In broader terms, the results from this research  are expected to find applications in scientific and engineering calculations that involve solving system of nonlinear equations or optimization (minimization or maximization) of certain quantities. The training component (for graduate/undergraduate training) of this research will contribute  to the pool of highly qualified personnel (HQP) in Canada. All of the trainees supported by the past discovery grants went on (or currently considering) to undertake graduate studies (at M.Sc. or Ph.D. level) or are actively contributing to the Canadian Industry (e.g., Syncrude, Telus, University of Lethbridge).