A Las Vegas randomized algorithm is given to compute the Hermite normal form of a nonsingular integer matrix A of dimension n . The algorithm uses quadratic integer multiplication and cubic matrix multiplication and has running time bounded by O(n 3 (log n + log ||A||) 2 (log n ) 2 ) bit operations, where || A ||= max ij | A ij | denotes the largest entry of A in absolute value. A variant of the algorithm that uses pseudo-linear integer multiplication is given that has running time (n 3 log || A ||) 1+ o (1) bit operations, where the exponent “ + o (1)” captures additional factors c 1 (log n ) c2 (loglog|| A ||) c3 for positive real constants c 1 ,c 2 ,c 3 .

Consider an integer matrix A ε Znx(n-1) that has full column rank n-1. The set of all Z-linear combinations of the rows of A generates a lattice, denoted by L(A).

We present a Las Vegas randomized algorithm to compute the Smith normal form of a nonsingular integer matrix. For an A ∈ Zn×n, the algorithm requires O(n3(log n + log ||A||)2 (log n)2) bit operations using standard integer and matrix arithmetic, where ||A|| = maxij |Aij | denotes the largest entry in absolute value. Fast integer and matrix multiplication can also be used, establishing that the Smith form can be computed in about the same number of bit operations as required to multiply two matrices of the same dimension and size of entries as the input matrix.

We present a deterministic reduction to matrix multiplication for the problem of linear system solving: given as input a nonsingular A \in \Z^n \times n and b \in \Z^n \times 1 , compute A^-1 b. We give an algorithm that computes the minimal integer e such that all denominators of the entries in 2^eA^-1 are relatively prime to 2. Then, for a b that has entries with bitlength O(n) times as large as the bitlength of entries in A, we give an algorithm to produce the 2-adic expansion of 2^eA^-1 b up to a precision high enough such that A^-1 b over \Q can be recovered using rational number reconstruction. Both e and the 2-adic expansion can be computed in O(\MM(n,łog n + łog ||A||) \times (łog n) (łog n + łoglog ||A||)) bit operations. Here, ||A||= \max_ij |A_ij | and \MM(n,d) is the cost to multiply together, modulo 2^d, two n \times n integer matrices. Our approach is based on the previously known reductions of linear system solving to matrix multiplication which use randomization to find an integer lifting modulus X that is relatively prime to \det A. Here, we derandomize by first computing a permutation P, a unit upper triangular M, and a diagonal S with \det S a power of two, such that U := APMS^-1 is an integer matrix with 2 \perp \det U. This allows our modulus X to be chosen a power of 2.

Consider solving a black box linear system, A(u) x = b(u), where the entries are polynomials in u over a field K, and A(u) is full rank. The solution, x = 1/g(u) f(u), where g is always the least common monic denominator, can be found by evaluating the system at distinct points ξl in K. The solution can be recovered even if some evaluations are erroneous. In [Boyer and Kaltofen, Proc. SNC 2014] the problem is solved with an algorithm that generalizes Welch/Berlekamp decoding of an algebraic Reed-Solomon code. Their algorithm requires the sum of a degree bound for the numerators plus a degree bound for the denominator of the solution. It is possible that the degree bounds input to their algorithm grossly overestimate the actual degrees. We describe an algorithm that given the same inputs uses possibly fewer evaluations to compute the solution. We introduce a second count for the number of evaluations required to recover the solution based on work by Stanley Cabay. The Cabay count includes bounds for the highest degree polynomial in the coefficient matrix and right side vector, but does not require solution degree bounds. Instead our algorithm iterates until the Cabay termination criterion is reached. At this point our algorithm returns the solution. Assuming we have the actual degrees for all necessary input parameters, we give the criterion that determines when the Cabay count is fewer than the generalized Welch/Berlekamp count.

Let F[∂ ; σ, δ] be a ring of Ore polynomials over a field. We give a new deterministic algorithm for computing the Popov form P of a non-singular matrix A ∈ F[∂ ; σ, δ]n x n. Our main focus is to ensure controlled growth in the size of coefficients from F in the case F = K(z), and even K = Q. Our algorithms are based on constructing from A a linear system over F and performing a structured fraction-free Gaussian elimination. The algorithm is output sensitive, with a cost that depends on the orthogonality defect of the input matrix: the sum of the row degrees in A minus the sum of the row degrees in P. The resulting bit-complexity for the differential and shift polynomial case over Q(z) improves upon the previous best.

Although randomized algorithms have widely been used in distributed computing as a means to tackle impossibility results, it is currently unclear what type of randomization leads to the best performance in such algorithms. This paper proposes three automated techniques to find the probability distribution that achieves minimum average recovery time for an input randomized distributed self-stabilizing protocol without changing the behavior of the algorithm. Our first technique is based on solving symbolic linear algebraic equations in order to identify fastest state reachability in parametric discrete-time Markov chains. The second approach applies parameter synthesis techniques from probabilistic model checking to compute the rational function describing the average recovery time and then uses dedicated solvers to find the optimal parameter valuation. The third approach computes over- and under-approximations of the result for a given parameter region and iteratively refines the regions with minimal recovery time up to the desired precision. The latter approach finds sub-optimal solutions with negligible errors, but it is significantly more scalable in orders of magnitude as compared to the other approaches.

We describe how to solve simultaneous Padé approximations over a power series ring K[[x]] for a field K using O~(nω - 1 d) operations in K, where d is the sought precision and $n$ is the number of power series to approximate. We develop two algorithms using different approaches. Both algorithms return a reduced sub-bases that generates the complete set of solutions to the input approximations problem that satisfy the given degree constraints. Our results are made possible by recent breakthroughs in fast computations of minimal approximant bases and Hermite Padé approximations.

We consider a variation of the well known problem of computing the unique solution to a nonsingular system Ax=b of n linear equations over a field K. The variation assumes that A has generic rank profile and requires as output not only the single solution vector A-1b Ε Kn x 1, but rather the solution to all leading principle subsystems. Most importantly, the rows of the augmented system [A||b] are given one at a time from first to last, and as soon as the next row is given the solution to the next leading principal subsystem should be produced. We call this problem ONLINESYSTEM. The obvious iterative algorithm for ONLINESYSTEM has a cost in terms of field operations that is cubic in the dimension of A. In this paper we introduce a relaxed representation for the inverse and show how to obtain an algorithm for ONLINESYSTEM that allows us to incorporate matrix multiplication. As an application we show how to introduce fast matrix multiplication into the inherently iterative algorithm for row rank profile computation presented previously by the authors.

Randomized algorithms are given for linear algebra problems on an input matrix A ∈ Knxm over a field K. We give an algorithm that simultaneously computes the row and column rank profiles of A in 2r3 + (r2 + n + m + |A|)1+o(1) field operations from K, where r is the rank of A and |A| denotes the number of nonzero entries of A. Here, the +o(1) in cost estimates captures some missing log n and log m factors. The rank profiles algorithm is randomized of the Monte Carlo type: the correct answer will be returned with probability at least 1/2. Given a b ∈ Knx1, we give an algorithm that either computes a particular solution vector x ∈ Kmx1 to the system Ax = b, or produces an inconsistency certificate vector u ∈ K1xn such that uA = 0 and ub ≠ 0. The linear solver examines at most r + 1 rows and r columns of A and has running time 2r3 + (r2 + n + m + |R| + |C|)1+o(1) field operations from K, where |R| and |C| are the number of nonzero entries in the rows and columns, respectively, that are examined. The solver is randomized of the Las Vegas type: an incorrect result is never returned but the algorithm may report FAIL with probability at most 1/2. These cost estimates are achieved by making use of a novel randomized online data structure for the detection of linearly independent rows and columns.

We present a new heuristic algorithm for computing the determinant of a nonsingular n x n integer matrix. Extensive empirical results from a highly optimized implementation show the running time grows approximately as n3 log n, even for input matrices with a highly nontrivial Smith invariant structure. We extend the algorithm to compute the Hermite form of the input matrix. Both the determinant and Hermite form algorithm certify correctness of the computed results.

The asymptotically fastest algorithms for many linear algebra problems on integer matrices, including solving a system of linear equations and computing the determinant, use high-order lifting. Currently, high-order lifting requires the use of a randomized shifted number system to detect and avoid error-producing carries. By interleaving quadratic and linear lifting, we devise a new algorithm for high-order lifting that allows us to work in the usual symmetric range modulo p, thus avoiding randomization. As an application, we give a deterministic algorithm to assay if an n x n integer matrix A is unimodular. The cost of the algorithm is O((log n)nω M(log n + log||A||)) bit operations, where ||A|| denotes the largest entry in absolute value, and M(t) is the cost of multiplying two integers bounded in bit length by t.

In this paper we present a deterministic algorithm for the computation of a minimal nullspace basis of an m x n input matrix of univariate polynomials over a field K with m ≤ n. This algorithm computes a minimal nullspace basis of a degree d input matrix with a cost of O~ (nω ⌈md/n⌉) field operations in K. Here the soft-O notation is Big-O with log factors removed while ω is the exponent of matrix multiplication. The same algorithm also works in the more general situation on computing a shifted minimal nullspace basis, with a given degree shift [equation] whose entries bound the corresponding column degrees of the input matrix. In this case if ρ is the sum of the m largest entries of s, then a s-minimal right nullspace basis can be computed with a cost of O~(nωρ/m) field operations.

The final step of some algebraic algorithms is to reconstruct the common denominator d of a collection of rational numbers (ni/d)1≤ i≤ n from their images (ai)1≤ i≤ n mod M, subject to a condition such as 0 < d ≤ N and Ni}≤ N for a given magnitude bound N. Applying elementwise rational number reconstruction requires that M ∈ Ω(N2). Using the gradual sublattice reduction algorithm of van Hoeij and Novocin, we show how to perform the reconstruction efficiently even when the modulus satisfies a considerably smaller magnitude bound M ∈ Ω(N1+1/c) for c a small constant, for example 2 ≤ c ≤ 5. Assuming c ∈ O(1) the cost of the approach is O(n(log M)3) bit operations using the original LLL lattice reduction algorithm, but is reduced to O(n(log M)2) bit operations by incorporating the L2 variant of Nguyen and Stehle. As an application, we give a robust method for reconstructing the rational solution vector of a linear system from its image, such as obtained by a solver using p-adic lifting.

This paper presents a new algorithm for computing the Hermite form of a polynomial matrix. Given a nonsingular n x n matrix A filled with degree d polynomials with coefficients from a field, the algorithm computes the Hermite form of A using an expected number of (n3d)1+o(1) field operations. This is the first algorithm that is both softly linear in the degree d and softly cubic in the dimension n. The algorithm is randomized of the Las Vegas type.

This paper gives gives a deterministic algorithm to transform a row reduced matrix to canonical Popov form. Given as input a row reduced matrix R over K[x], K a field, our algorithm computes the Popov form in about the same time as required to multiply together over K[x] two matrices of the same dimension and degree as R. We also show that the problem of transforming a row reduced matrix to Popov form is at least as hard as polynomial matrix multiplication.

Let M = [A B/C D] be a 2n x 2n integer matrix with the principal block A square and nonsingular. An algorithm is presented to determine if the Schur complement D--CA--1 B is equal to the zero matrix in O~(nω log ||M||) bit operations. Here, ω is the exponent of matrix multiplication and ||M|| denotes the largest entry in absolute value. The algorithm is randomized of the Las Vegas type, and either returns the correct answer ("yes" or "no"), or returns fail with probability less than 1/2. This gives a Las Vegas algorithm for computing the rank r of an n x m integer matrix A in an expected number of O~(nmrω--2 log ||A||) bit operations.

Efficient block projections of non-singular matrices have recently been used by the authors in [10] to obtain an efficient algorithm to find rational solutions for sparse systems of linear equations. In particular a bound ofO~(n2.5) machine operations is presented for this computation assuming that the input matrix can be multiplied by a vector with constant-sized entries using O~(n) machine operations. Somewhat more general bounds for black-box matrix computations are also derived. Unfortunately, the correctness of this algorithm depends on the existence of efficient block projections of non-singular matrices, and this was only conjectured.

A new randomized algorithm is presented for computing the characteristic polynomial of an n x n matrix over a field. Over a suffciently large field the asymptotic expected complexity of the algorithm is O(nθ)field operations, improving by a factor of log n on the worst case complexity of Keller-Gehrig's algorithm [11].

We propose a new algorithm to find a rational solution to a sparse system of linear equations over the integers. This algorithm is based on a p-adic lifting technique combined with the use of block matrices with structured blocks. It achieves a sub-cubic complexity in terms of machine operations subject to a conjecture on the effectiveness of certain sparse projections. A LinBox-based implementation of this algorithm is demonstrated, and emphasizes the practical benefits of this new method over the previous state of the art.

Algorithms for solving linear systems of equations over the integers are designed and implemented. The implementations are based on the highly optimized and portable ATLAS/BLAS library for numerical linear algebra and the GNU Multiple Precision library (GMP) for large integer arithmetic.

We reduce the problem of computing the rank and a null-space basis of a univariate polynomial matrix to polynomial matrix multiplication. For an input n x n matrix of degree, d over a field K we give a rank and nullspace algorithm using about the same number of operations as for multiplying two matrices of dimension, n and degree, d. If the latter multiplication is done in MM(n,d)= O~(nωd operations, with ω the exponent of matrix multiplication over K, then the algorithm uses O~MM(n,d) operations in, K. For m x n matrices of rank r and degree d, the cost expression is O(nmr ω-2d). The soft-O notation O~ indicates some missing logarithmic factors. The method is randomized with Las Vegas certification. We achieve our results in part through a combination of matrix Hensel high-order lifting and matrix minimal fraction reconstruction, and through the computation of minimal or small degree vectors in the nullspace seen as a K[x]-module.

New algorithms are presented for computing the dispersion set of two polynomials over Q and for shiftless factorization. Together with a summability criterion by Abramov, these are applied to get a polynomial-time algorithm for indefinite rational summation, using a sparse representation of the output.

The well-known technique of adic-lifting for linear-system solution is studied. Some new methods are developed and applied to get algorithms for the following problems over the ring of univariate polynomials with coefficients from a field: rational system-solving, integrality certification and determinant/Smith-form computation. All algorithms are Las Vegas probabilistic.

A deterministic algorithm for computing the Frobenius canonical-form of a matrix over a field is described. A similarity transformation-matrix is recovered in the same time. The algorithm is nearly optimal, requiring about the same number of field operations as required for matrix multiplication. Previously-known reductions to matrix multiplication are probabilistic.

A deterministic algorithm is presented for computing a particular solution to a linear system of equations with polynomial coefficients. Given an A ∈ F[x]n × m and b ∈ F[x]n, where F is a field, the algorithm will either return a particular solution v ∈ F(x)m to the system Av = b or determine that the system is inconsistent. The cost of the algorithm is O((n + m)r2d1 + ε) field operations from F, where r is the rank of A and d - 1 is a bound for the degrees of entries in A and b.

A sinq)lo randoruixed algorithnl is given for fillding an integer solubion to a s:-stclu of linear Di01)lmnt,ine equations.Givcu as input a s?;stcrrl which admits an int.cger solul.ion, the id- gorithru can 1~ used t,o find such a.solution wit,h probabilit~~ ilt least l/2.The running time (nunlber of bit operations) is esscntiall~ cubic in the dimemion of the s?;stem.The malogous result is prcsentctl for 1inca.rspst.cnls over the ring of polqonlials wit.li coefficients from a field.

Article The modulo N extended GCD problem for polynomials Share on Authors: Thom Mulders Institute of Scientific Computing, ETH Zurich, Switzerland Institute of Scientific Computing, ETH Zurich, SwitzerlandView Profile , Arne Storjohann Institute of Scientific Computing, ETH Zurich, Switzerland Institute of Scientific Computing, ETH Zurich, SwitzerlandView Profile Authors Info & Claims ISSAC '98: Proceedings of the 1998 international symposium on Symbolic and algebraic computationAugust 1998 Pages 105–112https://doi.org/10.1145/281508.281586Online:01 August 1998Publication History 0citation254DownloadsMetricsTotal Citations0Total Downloads254Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article An O(n3) algorithm for the Frobenius normal form Share on Author: Arne Storjohann Institute of Scientific Computing, ETH Zurich, Switzerland Institute of Scientific Computing, ETH Zurich, SwitzerlandView Profile Authors Info & Claims ISSAC '98: Proceedings of the 1998 international symposium on Symbolic and algebraic computationAugust 1998 Pages 101–105https://doi.org/10.1145/281508.281570Online:01 August 1998Publication History 20citation1,405DownloadsMetricsTotal Citations20Total Downloads1,405Last 12 Months39Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper considers a variation of the extended gcd problem: the "modulo N extended gcd problem", Given an integer row vector [a, ]~=1.the modulo N extended gcd problem asks for an integer vector [c,]~=l such that n gcd(~c, a,, N) = gcd(al, a~, . ..,a~,N) ,:1 A deterministic algorithm is presented which returns an exceptionally small solution for a given instance of the problem: both ma.x~=~Ic,I and the number of nonzero c,'s will he boundedbyO(logN).The gcd algorithm presented here has numerou supplications andhaa already ledtofasteralgorithms for computing row reduced echelon forms of integer matrices and solving systems of linear Diophantine equations.III this paper we show how to apply our g,cd algorithm to the problem of computing small pre-and post-multipliers for the Smith normal of an integer matrix."'rbis work has been partially supported by grants from the Swiss Federal Ofiice for Education and Sciences in conjunction with partial support by ESPRIT LTR

We present new algorithms for computing Smith normal forms of matrices over the integers and over the integers modulo d. For the case of matrices over ZZ d , we present an algorithm that computes the Smith form S of an A 2 ZZ n\\Thetam d in only O(n `\\Gamma1 m) operations from ZZ d . Here, ` is the exponent for matrix multiplication over rings: two n \\Theta n matrices over a ring R can be multiplied in O(n ` ) operations from R. We apply our algorithm for matrices over ZZ d to get an algorithm for computing the Smith form S of an A 2 ZZ n\\Thetam in O~(n `\\Gamma1 m \\Delta M(n log jjAjj)) bit operations (where jjAjj = max jA i;j j and M(t) bounds the cost of multiplying two dte-bit integers). These complexity results improve significantly on the complexity of previously best known Smith form algorithms (both deterministic and probabilistic) which guarantee correctness. 1 Introduction The Smith normal form is a canonical diagonal form for equivalence of matrices over a princ...

This paper presents a new algorithm for computing the Hermite normal form H of an A c Z "m of rank m together with a unimodular pre-multiplier matrix U such that UA = H.Our algorithm requires O-(m '-lnM(mlog[lAl\)) bit oper@ions to produce both H and U. Here, IIAII = max,j lAij [, M(t) bit operations are sufficient to multiply two (t] -bit integers, and 0 is the exponent for matrix multiplication over rings: two m x m matrices over a ring R can be multiplied in O(me ) ring operations from R, The previously fastest algorithm of Hafner & McCurley requires 0-(m2nM (m log I IAI [)) bit operations to produce H, but does not produce a unimodular matrix U which satisfies UA = H.Previous methods require on the order of 0-(n3M(m log I[Al 1)) bit operations to produce a U -our algorithm improves on this significantly in both a theoretical and practical sense.

We present a Las Vegas probabilistic algorithm for reducing the computation of Hermite normal forms of rectangular polynomial matrices.In particular, the problem of computing the Hermite normal form of a rectangular m x n matrix (with m > n) reduces to that of computing the Hermite normal form of a matrix of size (n + 1) x n having entries of similar coefficient size and degree.The main cost of the reduction is the same as the cost of fraction-free Gaussian elimination of an m x n polynomial matrix.As an application, the reduction allows for the efficient computation of one-sided GCD'S of two matrix polynomials along with the solution of the matrix diophantine equation associated to such a GCD.