Grant: Discovery Grants Program - Individual
University of Calgary
$27,000.00
Randomized matrix computations over finite fields
EF 2008-09
Résumé
A goal of my research is to design and analyze algorithms for problems in linear algebra. In recent years I have concentrated on algorithms that use randomization, in some way, to solve systems of linear equations over small finite fields. The algorithms that I study are inspired by (and, ideally, closely resemble) methods that are reportedly being used effectively to solve problems in computational number theory - which, in turn, are needed for cryptographic applications - but whose efficiency or reliability has not been rigorously established.
The results that I hope to obtain could serve to identify, and overcome, problems with the use of these algorithms that are not necessarily evident as they are presently used but that could cause computations to fail if the algorithms were used to solve a wider variety of problems. This type of work is necessary if these algorithms are to be included in computer algebra systems like Maple or Mathematica and made readily available for widespread use.
The particular work that I am now doing, and propose to continue, is in an area that lacks generally useful techniques for the analysis of the reliability of algorithms. This complicates my work but also makes it potentially more useful: It forces me to work to develop new techniques that would be of use for other researchers who are also working to solve this type of problem.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Alberta, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
89756-2008
Name nom
Eberly, Wayne
Department département
Computer Science
Organization id
11
Institution établissement
University of Calgary
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2008
Competition year année de concours
2008
Award amount
27000
Program id
RGPIN
Program nane 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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
1
Nb partie
5
Application title
Randomized matrix computations over finite fields
Keyword
NA
Application summary
A goal of my research is to design and analyze algorithms for problems in linear algebra. In recent years I have concentrated on algorithms that use randomization, in some way, to solve systems of linear equations over small finite fields. The algorithms that I study are inspired by (and, ideally, closely resemble) methods that are reportedly being used effectively to solve problems in computational number theory - which, in turn, are needed for cryptographic applications - but whose efficiency or reliability has not been rigorously established.
The results that I hope to obtain could serve to identify, and overcome, problems with the use of these algorithms that are not necessarily evident as they are presently used but that could cause computations to fail if the algorithms were used to solve a wider variety of problems. This type of work is necessary if these algorithms are to be included in computer algebra systems like Maple or Mathematica and made readily available for widespread use.
The particular work that I am now doing, and propose to continue, is in an area that lacks generally useful techniques for the analysis of the reliability of algorithms. This complicates my work but also makes it potentially more useful: It forces me to work to develop new techniques that would be of use for other researchers who are also working to solve this type of problem.