Reducing ideal arithmetic to linear algebra problems (Q3840172)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1186950
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Reducing ideal arithmetic to linear algebra problems |
scientific article; zbMATH DE number 1186950 |
Statements
4 May 2000
0 references
ideal arithmetic
0 references
modular linear algebra
0 references
0.7809854745864868
0 references
0.7436014413833618
0 references
Reducing ideal arithmetic to linear algebra problems (English)
0 references
Most (implemented) algorithms in number theory rely on ideal arithmetic that is usually reduced to computations in free \(\mathbb{Z}\)-modules \(\Lambda\). In this context usually one knows a common multiplier \(m\) for the modules involved, i.e. \(m\mathbb{Z}^n\subset \Lambda \subset \mathbb{Z}^n\). Using this fact one can reduce the linear algebra in \(\mathbb{Z}\) to linear algebra in \(\mathbb{Z}/m\mathbb{Z}\). Extending ideas contained in [\textit{J. A. Howell}, Linear Multilinear Algebra 19, 67-77 (1986; Zbl 0596.15013)], the author gives procedures for determining the span and null space of matrices defined over \(\mathbb{Z}/m\mathbb{Z}\). The key ingredient is an extended gcd algorithm that is used to replace the inversions (that may fail) of the usual Gaussian elimination. As an application he gives explicit algorithms for ideal arithmetic in (the maximal) orders of extensions of \(\mathbb{Q}\), namely for the computation of the sum, intersection, product and quotient of ideals, whenever the operation is defined. For the entire collection see [Zbl 0891.00022].
0 references