新渐近快速算法：解决委托决定因素问题与矩阵运算

本文是一篇发表于2003年的研究报告，由Erih Kaltofen和Gilles Villard合作完成，两位作者分别来自北卡罗来纳州立大学和法国里昂高等师范学校的并行计算实验室。报告标题强调了“委托决定因素的多重性”这一主题，探讨了在并行计算领域中的一个重要问题——矩阵运算，特别是解决密集矩阵上的迪利克雷（Diophantine）问题，如分解或化简矩阵。 文中提到的关键算法，如Kaltofen（1992）的工作，以及Wiedemann（1986）和Coppersmith（1994）的贡献，都围绕着矩阵的BLOSUM投影和相关分析。研究的主要目标是设计一种新的渐近快速算法，能够在密集矩阵上实现高效的运算，比如在Frobenius和Smith正规形式间的转换。这个算法在处理二进制基数下的操作时，具有时间复杂度为O(n^3:2logkAk)1+o(1)和O(n^2:697263logkAk)1+o(1)，相较于传统方法显著提高效率。 值得一提的是，算法是非确定性的，采用的是概率性方法，如拉斯维加斯算法，这意味着它有可能需要多次尝试才能得到正确结果。然而，通过引入Coppersmith和Winograd的矩阵乘法技术，论文作者还展示了如何在O(n^2:697263)和O(n^2:806515)的操作复杂度下达到终止，并在特定环中执行加法、减法和乘法操作，而无需使用子泛矩阵乘积。 这篇论文对并行计算和数值代数中的核心问题进行了深入探索，不仅提升了算法性能，也为理解密集矩阵处理的优化策略提供了新的见解。通过结合概率性方法与高级数学工具，研究人员展示了在实际计算中如何逼近最优解，这对于处理大规模数据和优化计算负载具有重要意义。