Fast Linear Algebra Solver for Engineering Applications

该提案旨在开发一个新的线性代数工具集的理论和应用框架。在许多工程应用中，需要求解大型线性方程组。通常选择的方法是迭代方法，因为它们的速度快，并且具有其他有吸引力的计算特性。许多技术将问题转化为矩阵连续幂的求和。在这些情况下，总是假设欧拉分解对于这样一个求和是计算上最优的。该建议以一个具体的例子开始，表明情况并非如此，事实上，通常可以通过使用更有效的分解来节省大量的计算。如何准确地完成这种分解的设计是本文的理论要点之一。作为这项工作的一部分而设计的算法工具将有助于创建更高效的软件和硬件解决方案。在硬件方面，最直接的应用程序似乎是Goldschimdt浮点除法算法的优化实现。在目前广泛使用的64位处理器和下一代128位处理器的情况下，我们期望获得更有效的算法，并显着加快这一主要计算操作。在软件应用方面，我们可以应用本研究主要成果的实际情况是无限的。最直接的应用将是将新技术应用于各种类型的成像-地震，生物医学，分子等。特别感兴趣的是在地球物理领域的应用，因为在这些情况下，人们需要处理巨大尺寸的矩阵，正如最初的发现所表明的那样，问题的规模越大，我们节省的就越多。另一组可能的应用程序——其中一些结果已经被接受发表——是加密算法，它广泛使用有限域的反转。在其中一个案例中，我们已经报告了一种解决方案，它比文献中最著名的解决方案快44%；我们期望在更精确地应用本建议中建议的分解技术的基础上取得更好的结果。另一个可能的巨大应用是加速PageRaking算法（用于社交网络和搜索引擎应用）和GeneRaking算法（用于计算生物学应用）。*我们相信这是一个非常迷人的跨学科项目，将创造大量的软件和硬件工具，用于直接的工业应用。更重要的是，这项提案的工作将导致培养非常高质量的个人，无论是硕士还是博士水平，这将对加拿大经济非常有帮助。

The proposal is aimed at developing a theoretical and applied framework of a new linear algebra set of tools. In many engineering applications, one requires to solve large systems of linear equations. Often the method of choice are iterative methods, due to their fast speed and other attractive computational features. Many of the techniques convert the problems into a summation of consecutive powers of a matrix. In those cases it is always assumed that the Euler's decomposition for such a summation is computationally optimal. The proposal starts with a concrete example showing that this is not the case and, in fact, often one can get significant computational saving by using more efficient decompositions. Exactly how to accomplish the design of such decompositions is one of the theoretical points of this proposal. The algorithmic tools designed as a part of this work will help the creation of more efficient software and hardware solutions. In terms of hardware, the most straightforward application seems to be the optimized implementation of the Goldschimdt's floating point division algorithm. In the case of the widely used today 64-bit processor and the next-generation 128-bit processor, we anticipate to obtain much more efficient algorithms and significantly speed-up this major computational operation. In terms of software applications, the number of practical situations in which we can apply the main results of this research is unlimited. The most direct application will be the use of the novel techniques to various type of imaging - seismic, biomedical, molecular, etc. Of particular interests are the applications in geophysical domains, since in these cases one needs to process matrices of huge sizes and, as the initial findings suggest, the bigger the size of the problem, the more we save. Another possible set of applications - some results on that already accepted for publication - is cryptographic algorithms, that extensively use inversion of finite fields. In one of this cases we already reported a solution, that is 44% faster that the best known in the literature solutions; we anticipate even better results, based on more precise application of the decomposition techniques suggested in this proposal. Another possible - and huge - application, is the speeding up the PageRaking algorithms (for social networks and search engine applications) and GeneRaking algorithms (for computational biology applications).*We believe that this is a fascinating and very, very interdisciplinary project that will lead to creating a large number of software and hardware tools for direct industrial application. More to the point, the work on this proposal will lead to training very high-quality personal, both on MSs and PhD level, that will be extremely helpful for the canadian Economy.