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.