Name
Abstract | ||
|---|---|---|
As a canonical form for integer matrices, Hermite Normal Form (HNF) has been widely used in various fields such as computational number theory and cryptography. In previous algorithms, arithmetic modulo the determinant is usually used to control the intermediate numbers. In this paper, we propose a new technique to compute the HNF for integer matrices via solving a system of linear equations, with which we can control the intermediate numbers more tightly. Based on the technique, we present two new HNF algorithms. First we present a conceptually simpler algorithm. This algorithm is slow in practical and is intended only for illustrating the idea. Then we propose a practical hybrid algorithm. Under some reasonable assumption, the new algorithm has expected time complexity \widetildeO (n^ømegałog M). Here n^ømega is the number of arithmetic operations required to multiply two n\times n matrices and the currently best known value for ømega is approximately 2.373.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3326229.3326238 | Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation |
Keywords | Field | DocType |
hnf, linear space, solving system of linear equations | Hermite normal form,Discrete mathematics,Algebra,System of linear equations,Computer science | Conference |
ISBN | Citations | PageRank |
978-1-4503-6084-5 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Renzhang Liu | 1 | 0 | 0.34 |
| Yanbin Pan | 2 | 35 | 13.29 |