低复杂度极小误差数值算法研究

In high-performance computing, large-scale and long-time numerical calculations often produce inaccurate and invalidated results owing to cancellation from round-off errors. To deal with this problem, this project, based on error-free transformation, will analyze the accumulative effect of round-off errors in the floating point code level. After first proposing the conception of minimal-error algorithm, this project will study theoretical minimal error of the algorithm in the confirmed case by tensor analysis. Meanwhile, to some typical numerical algorithms, the project will analyze the algebraic structure and statistical properties of the round-off errors with multiple linear algebra and Bayesian method, and then design the minimal error algorithm. The project finally will consider using regional separatist theory to design the parallel low-complexity and minimal-error algorithms. The purpose of this project is enhancing the performance of LAPACK and ScaLAPACK and providing theoretical and technical support to build the next generation of the efficient and credible numerical algebra algorithm library. As a basic and common research of high-performance scientific computing, the project will greatly enhance the practical application of high-performance computers and promote the development of various fields, such as biology, ocean, atmosphere, and defense.

当前在高性能计算中，大规模、大尺度、长时程数值计算由于浮点计算的舍入误差累积效应，常导致不可信的数值结果。针对这一难以解决的常见问题，本项目运用无误差变换理论，从浮点运算代码层面上，分析舍入误差累积效应；并首次提出极小误差的新概念，通过引入应用张量分析理论，研究有限条件下数值算法所能达到的理论误差下界；针对若干典型数值算法，应用多重线性代数和贝叶斯推断方法，分析舍入误差累积在算法中的代数结构和统计特性，进而设计极小误差算法；应用区域分裂理论，设计相应的低复杂度并行极小误差数值算法。本项目研究成果可用于提升LAPACK和ScaLAPACK的性能，为建立下一代高效可信的数值代数算法库提供理论和技术支持。作为高性能科学计算底层基础研究，将极大提升我国高性能计算机的实际应用效率，推动生物、海洋、大气、国防等各领域的发展。

在高性能计算中，大规模工程科学计算由于浮点计算的舍入误差累积效应，常导致不可信的数值结果。设计高效的低复杂度极小误差数值算法将有效的解决这一问题。本项目主要应用无误差变换技术，结合高性能计算需求，针对若干数值代数问题展开研究。.本项目取得的主要成果有：（1）设计了两个极小误差数值算法库，即处理正交基多项式高精度计算的ORTHOPOLY和基于MATLAB的多部分格式的高精度基础函数算法库MPLAB；（2）设计了计算三类二维多项式函数的高精度快速算法；（3）针对ARMv8多核处理器，通过撰写优化的内核汇编代码，设计了高效的DGEMM实现、高精度CompDGEMM实现和四精度QGEMM实现（4）针对单位对称函数，提出了高精度补偿Summation算法 (5) 针对商-差qd算法,提出了高精度补偿qd算法，并成功应用到求连分式系数、求亚纯函数极点和多项式零点等。上述相关实现的优化算法都较原算法有明显的精度提升，且比其它数值精度提升手段有明显的计算效率优势。.本项目研究期间共发表论文15篇，其中SCI源刊6篇，EI检索7篇；获国防发明专利授权1项。圆满完成了任务书中对研究结果的预期。