The exact probability, dependent on the matrix structure, is given that the block Wiedemann algorithm correctly computes the leading invariant factors of a matrix. A tight lower bound, structure independent, is derived.

One useful standard method to compute eigenvalues of matrix polynomials P(z)∈ C n x n [z] of degree at most ℓ in z (denoted of grade ℓ, for short) is to first transform P(z) to an equivalent linear matrix polynomial L(z)=zB-A, called a companion pencil, where A and B are usually of larger dimension than P(z) but L(z) is now only of grade 1 in z. The eigenvalues and eigenvectors of L(z) can be computed numerically by, for instance, the QZ algorithm. The eigenvectors of P(z), including those for infinite eigenvalues, can also be recovered from eigenvectors of L(z) if L(z) is what is called a "strong linearization'' of P(z). In this paper we show how to use algorithms for computing the Hermite Normal Form of a companion matrix for a scalar polynomial to direct the discovery of unimodular matrix polynomial cofactors E(z) and F(z) which, via the equation E(z)L(z)F(z) = diag(P(z), In, …, I_n), explicitly show the equivalence of P(z) and P(z). By this method we give new explicit constructions for several linearizations using different polynomial bases. We contrast these new unimodular pairs with those constructed by strict equivalence, some of which are also new to this paper. We discuss the limitations of this experimental, computational discovery method of finding unimodular cofactors.

Matrices with two nonzero entries per row (or per column) occur in many contexts. For example, edge-vertex incidence matrices of graphs have this form. Also, the boundary matrix for the highest dimensional simplices in a simplicial complex sometimes has this form as well. In particular, the homology of a triangulation of a 2 dimensional non-self-intersecting surface is obtained from the Smith forms of 2 two-per-row matrices (the edge-vertex and triangle-edge boundary matrices).

We present algorithms to compute the Smith Normal Form of matrices over two families of local rings. The algorithms use the black-box model which is suitable for sparse and structured matrices. The algorithms depend on a number of tools, such as matrix rank computation over finite fields, for which the best-known time- and memory-efficient algorithms are probabilistic.

We present certificates for the positive semidefiniteness of an n by n matrix A, whose entries are integers of binary length log ||A||, that can be verified in O(n(2+µ) (log ||A||)(1+µ) binary operations for any µ > 0. The question arises in Hilbert/Artin-based rational sum-of-squares certificates (proofs) for polynomial inequalities with rational coefficients. We allow certificates that are validated by Monte Carlo randomized algorithms, as in Rusins Freivalds's famous 1979 quadratic time certification for the matrix product. Our certificates occupy O(n(3+µ) (log ||A||)(1+µ) bits, from which the verfication algorithm randomly samples a quadratic amount.

An iterative refinement approach is taken to rational linear system solving. Such methods produce, for each entry of the solution vector, a rational approximation with denominator a power of 2. From this the correct rational entry can be reconstructed. Our iteration is a numeric-symbolic hybrid in that it uses an approximate numeric solver at each step together with a symbolic (exact arithmetic) residual computation and symbolic rational reconstruction. The rational solution may be checked symbolically (exactly). However, there is some possibility of failure of convergence, usually due to numeric ill-conditioning. Alternatively, the algorithm may be used to obtain an extended precision floating point approximation of any specified precision. In this case we cannot guarantee the result by rational reconstruction and an exact solution check, but the approach gives evidence (not proof) that the probability of error is extremely small. The chief contributions of the method and implementation are (1) confirmed continuation, (2) improved rational reconstruction, and (3) faster and more robust performance.

We present algorithms and heuristics to compute the characteristic polynomial of a matrix given its minimal polynomial. The matrix is represented as a black-box, i.e., by a function to compute its matrix-vector product. The methods apply to matrices either over the integers or over a large enough finite field. Experiments show that these methods perform efficiently in practice. Combined in an adaptive strategy, these algorithms reach significant speedups in practice for some integer matrices arising in an application from graph theory.

For the problem of computing the rank of a matrix we have a complexity result and a practical implementation, both of which apply best to the case of a matrix whose rank is substantially smaller than its order.

We present algorithms for computing the p-rank of integer matrices. They are designed to be particularly effective when p is a small prime, the rank is relatively low, and the matrix itself is large and dense and may exceed virtual memory space. Our motivation comes from the study of difference sets and partial difference sets in algebraic design theory. The p-rank of the adjacency matrix of an associated strongly regular graph is a key tool for distinguishing difference set constructions and thus answering various existence questions and conjectures. For the p-rank computation, we review several memory efficient methods, and present refinements suitable to the small prime, small rank case. We give a new heuristic approach that is notably effective in practice as applied to the strongly regular graph adjacency matrices. It involves projection to a matrix of order slightly above the rank. The projection is extremely sparse, is chosen according to one of several heuristics, and is combined with a small dense certifying component. Our algorithms and heuristics are implemented in the LinBox library. We also briefly discuss some of the software design issues and we present results of experiments for the Paley and Dickson sequences of strongly regular graphs.

A key step in the computation of the unitary dual of a Lie group is the determination if certain rational symmetric matrices are positive semi-definite. The size of some of the computations dictates that high performance integer matrix computations be used. We explore the feasibility of this approach by developing three algorithms for integer symmetric matrix signature and studying their performance both asymptotically and experimentally on a particular matrix family constructed from the exceptional Weyl group E8. We conclude that the computation is doable, with a parallel implementation needed for the largest representations.

We present a variation of the fast Monte Carlo algorithm of Eberly, Giesbrecht and Villard for computing the Smith form of an integer matrix. It is faster in practice, but with the same asymptotic complexity, and it also handles the singular case. Then we will apply the key principle to improve Storjohann's algorithm and Iliopoulos' algorithm. We have a soft linear time algorithm for the special case of a diagonal matrix. A local Smith form Algorithm is also considered.We offer analysis and experimental results regarding these algorithms, with a view to the construction of an adaptive algorithm exploiting each algorithm at it's best range of performance. Finally, based on this information, we sketch the proposed structure of an adaptive Smith form algorithm for matrices over the integers. Our experiments use implementations in LinBox, a library for exact computational linear algebra available at linalg.org.

We present algorithms to construct an efficient black box for the pseudoinverse, At, of a black box matrix A. This in also known as the Moore-Penrose inverse of A. For the system Ax = b over a subfield of the complex numbers: the vector x = Atb is the least squares solution having the least norm. When we say that A is a black box matrix we mean simply that methods are given to compute the matrix-vector products Au and uTA, for vectors u and vectors v of compatible length. No other assumptions are made about the structure or representation of the matrix.

We present a new algorithm to compute the Integer Smith normal form of large sparse matrices. We reduce the computation of the Smith form to independent, and therefore parallel, computations modulo powers of word-size primes. Consequently, the algorithm does not suffer from coefficient growth. We have implemented several variants of this algorithm (Elimination and/or Black-Box techniques) since practical performance depends strongly on the memory available. Our method has proven useful in algebraic topology for the computation of the homology of some large simplicial complexes.

Randomized black b o x algorithms provide a very ecient means for solving sparse linear systems over arbitrary elds.However, when these probabilistic algorithms fail, it is not revealed whether no solution exists or whether the algorithm simply made unlucky random choices.Here we give a n ecient algorithm to compute a certi cate of inconsistency for a black b o x linear system over a eld.Our method requires a black box for the transpose of the matrix.The cost of producing the certi cate is shown to be about the same as that of solving the system in the black b o x model, while the cost of applying a given certi cate to prove inconsistency is much smaller.We also give an ecient algorithm for certifying that a sparse Diophantine linear system of integer equations has no integer solutions, even when it may h a v e rational solutions.

In this paper, we consider the problem of interpolating univariate polynomials over a field of characteristic zeros that are sparse in (a) the Pochhammer basis, or (b) the Chebyshev basis. The polynomials are assumed to be given by black boxes, i.e., one can obtain the value of a polynomial at any point by querying its black box. We describe efficient new algorithms for these problems. Our algorithms may be regarded as generalizations of Ben-Or and Tiwari’s (1988) algorithm (based on the BCH decoding algorithm) for interpolating polynomials that are sparse in the standard basis. The arithmetic complexity of the algorithms is $O(t^{2} + t \log d)$, which is also the complexity of the univariate version of the Ben-Or and Tiwari algorithm. That algorithm and those presented here also share the requirement of $2t$ evaluation points.

) Introduction In this paper, we consider the problem of computing t-sparse shifts for univariate polynomials. Given a polynomial f(x) 2 F [x] of degree d (where F is a field of characteristic 0), consider the representation of f(x) in the basis 1; x \\Gamma ff; (x \\Gamma ff) 2 ; . . . for some ff 2 K; an extension of F ; i.e., f(x) = d X i=0 f i (x \\Gamma ff) i : Let t be a positive integer d: We say that ff is a t-sparse shift for f(x) (or, f(x) is t-sparse in the shifted basis 1; x \\Gamma ff; (x \\Gamma ff) 2 ; . . .) if at most t of the coefficients f i are non-zero. The main problem that we address is: given an f(x) and t as above, can we efficiently compute a t-sparse shift for f(x) if one exists? We construct an efficient algorithm for solving this problem and answer several related questions of interest, such as: When is a shift unique? When is a shift rational (meaning when does ff 2 F?)? How many evaluations does one need to distinguish 2 polynomials that are shi...

In this paper, we describe a parallelization scheme for Collins' cylindrical algebraic decomposition algorithm for quantifier elimination in the theory of real closed fields. We first discuss a parallel implementation of the computer algebra system SAC2 in which a complete sequential implementation of Collins' algorithm already exists. We report some initial results on the speedup obtained, drawing on a suite of examples previously given by Arnon.

In Part I of this paper, we give an extension of Liouville’s Theorem and give a number of examples which show that integration with special functions involves some phenomena that do not occur in integration with the elementary functions alone. Our main result generalizes Liouville’s Theorem by allowing, in addition to the elementary functions, special functions such as the error function, Fresnel integrals and the logarithmic integral (but not the dilogorithm or exponential integral) to appear in the integral of an elementary function. The basic conclusion is that these functions, if they appear, appear linearly. We give an algorithm which decides if an elementary function, built up using only exponential functions and rational operations has an integral which can be expressed in terms of elementary functions and error functions.

A class of univariate polynomials is defined which make the Berlekamp-Hensel factorization algorithm take an exponential amount of time. This class contains as subclasses the Swinnerton-Dyer polynomials discussed by Berlekamp and a subset of the cyclotomic polynomials. Aside from shedding light on the complexity of polynomial factorization this class is also useful in testing implementations of the Berlekamp–Hensel and related algorithms.