High-order lifting and integrality certification (Q1878491): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q587229 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Willy Govaerts / rank | |||
Normal rank |
Revision as of 17:45, 19 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | High-order lifting and integrality certification |
scientific article |
Statements
High-order lifting and integrality certification (English)
0 references
20 August 2004
0 references
The author studies some classical problems that involve a nonsingular matrix \(A\in K[x]^{n\times n}\) over the ring \(K[x]\) of univariate polynomials with coefficients from a field \(K\) and proves that they can be solved at approximately the same cost as that for matrix multiplication. The most fundamental of these is linear system solving, i.e. to compute the solution to \(Ax=b\) where \(b\in K[x]^{n\times n}\). The second is integrality certification, i.e. to answer the following question: If \(B\in K[x]^{n\times m}\) is given, can every column of \(B\) be expressed as a \(K[x]\)-linear combination of the columns of \(A\)? The third problem is determinant computation. For this the author proposes a Las Vegas probabilistic algorithm whose expected number of operations is an order of magnitude smaller than the best known deterministic method. In the same time the Smith form of the matrix is computed.
0 references
determinant
0 references
Smith canonical form
0 references
linear system
0 references
polynomial matrix
0 references
integrality certification
0 references
Las Vegas probabilistic algorithm
0 references