DocumentCode :
2523575
Title :
A Vector Implementation of Gaussian Elimination over GF(2): Exploring the Design-Space of Strassen´s Algorithm as a Case Study
Author :
Morancho, Enric
Author_Institution :
Dept. d´Arquit. de Computadors, Univ. Politec. de Catalunya, Barcelona, Spain
fYear :
2015
fDate :
4-6 March 2015
Firstpage :
111
Lastpage :
118
Abstract :
Gaussian elimination is a key algorithm in linear algebra. It has many usages, for instance solving systems of linear equations and determining whether a set of vectors is linearly independent. This algorithm transforms an input matrix into a matrix in row (column) echelon form. The matrix entries and the transformations are defined over algebraic fields either infinite (e.g. the real numbers) or finite (e.g. GF (2)). This work discusses a vector implementation of this algorithm over GF (2). The evaluation develops a case study that searches exhaustively for algorithms over GF (2) similar to Strassen´s algorithm (a matrix-multiply algorithm with sub cubic complexity) because the search engine requires solving a huge number of Gaussian eliminations over GF (2). Our vector implementation allows the search engine to complete the exploration in less than nine hours on a commodity processor supporting AVX2, outperforming by 1.92X a scalar-SWAR implementation specialized for the case study and by 7.43X a generic scalar-SWAR implementation. Our results show that, over GF (2), there are 20 algorithms similar to Strassen´s.
Keywords :
Galois fields; Gaussian processes; mathematics computing; matrix algebra; vectors; 1.92X; 7.43X; AVX2; GF(2); Gaussian elimination; Strassen algorithm design-space; commodity processor; generic scalar-SWAR implementation; input matrix; linear algebra; linear equations; matrix-multiply algorithm; scalar-SWAR implementation; search engine; subcubic complexity; vector implementation; Algorithm design and analysis; Complexity theory; Layout; Registers; Search engines; Space exploration; Transforms; AVX2; GF(2); Gaussian elimination; Strassen´s algorithm; echelon form; vector implementation;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel, Distributed and Network-Based Processing (PDP), 2015 23rd Euromicro International Conference on
Conference_Location :
Turku
ISSN :
1066-6192
Type :
conf
DOI :
10.1109/PDP.2015.24
Filename :
7092708
Link To Document :
بازگشت