CAREER: Foundations for Understanding and Reaching the Limits of Standard Numerical Linear Algebra

更快的数值模拟是至关重要的，例如，在基础科学中实现新的科学发现，或在工程中开发革命性的新产品。这方面的大多数研究旨在开发新的算法实现来加速计算。这项研究并没有沿着这条路走下去，而是首先回答了一个问题：“我们可以将给定的计算加速多少？”那么，第二部分是开发能够达到这些最短时间限制的高效算法。我们的研究使我们更好地理解我们的算法及其内在局限性，并最终产生更好的、接近最优的算法。考虑到当前计算体系结构的复杂性和有待解决的问题，本研究的两个组成部分都代表了巨大的挑战。这项研究的结果将在本项目的综合教育部分进行交流，其中通过课堂、出版书籍、分发源代码和开发网络文件传播以前和最近的工作和方法。重要的分类和书目工作将在跨学科的数学/CS阅读课上进行。更广泛的推广活动在K-12教室进行，并通过丹佛大都会地区的公共STEM相关活动进行。本课题的研究包括三个部分。给定要解决的数值问题，研究者(1)开发一个特设模型，详细说明计算机器的理论限制，(2)模拟基于特设模型的算法的执行，(3)在目标架构上进行数值实验。研究者的方法在这三个组件之间进行迭代改进，直到它们匹配为止。每次改进都需要回答关于下界和算法的几个开放问题。

Faster numerical simulations are critical, for example, in basic science for enabling novel scientific discoveries, or in engineering for developing revolutionary new products. Most research in this vein aims to develop new algorithmitic implementations to accelerate computations. Rather than moving down that path, this research first answers the question: "by how much can we accelerate a given computation?" The second component, then, is to develop highly-efficient algorithms able to reach these minimum time limits. Our research leads to a better understanding of our algorithms and their intrinsic limitations, and eventually results in better, near-optimal algorithms. Both components of this research represent tremendous challenges given the complexity of the current computing architecture and the problem to be solved.The results of this research will be communicated in an integrated education component of this project in which previous and recent work and methodologies are disseminated through classes, the publication of a book, the distribution of source codes and the development of web documents. Important taxonomy and bibliographic work will be performed during interdisciplinary math/CS reading classes. Broader outreach activities are conducted in K-12 classrooms and through public STEM- related events in the metropolitan Denver area.The research in the project includes three components. Given a numerical problem to be solved, the investigator (1) develops an ad-hoc model detailing the theoretical limitations of the computational machine, (2) simulates the execution of an algorithm based on the ad-hoc model, and (3) conducts numerical experiments on the targeted architecture. The investigator's methodology applies iterate improvements between these three components until they match. Each improvement requires answering several open questions in terms of lower bounds and algorithms.