Fast Linear Algebra Solver for Engineering Applications

点击翻译按钮获取中文摘要

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.