Grant: Discovery Grants Program - Individual
University of Calgary
$25,000.00
Fast Linear Algebra Solver for Engineering Applications
FY 2016-17
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2014-03905
Name nom
Dimitrov, Vassil
Department département
Electrical and Computer Engineering
Organization id
11
Institution établissement
University of Calgary
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2014
Award amount
25000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1510
Committee name en
Electrical and Computer Engineering
Committee name fr
Génie électrique et informatique
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2955
Research subject group en
Applied mathematics
Research subject group fr
Mathématiques appliquées
Research subject en
Numerical analysis
Research subject fr
Analyse numérique
Partie
3
Nb partie
5
Application title
Fast Linear Algebra Solver for Engineering Applications
Keyword
NSERC
Application summary
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.