Fast Linear Algebra Solver for Engineering Applications

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

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.