Processes to automate the selection of appropriate algorithms for various matrix computations are described. In particular, processes to check for, and certify, various matrix properties of black-box matrices are presented. These include sparsity patterns and structural properties that allow "superfast" algorithms to be used in place of black-box algorithms. Matrix properties that hold generically, and allow the use of matrix preconditioning to be reduced or eliminated, can also be checked for and certified --- notably including in the small-field case, where this presently has the greatest impact on the efficiency of the computation.

A new block Lanczos algorithm for computations over small finite fields is presented and analysed. The algorithm can be used to solve a system of linear equations or sample uniformly from the null space whenever the number of nilpotent blocks with order at least two in the Jordan form of the given coefficient matrix is less than the block factor on the right. It can also be used to verify that this matrix condition is not satisfied, in order to confirm that preconditioning of the given matrix is required.

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.

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.

Blocked versions of the Lanczos procedure have been successfully applied to sample nullspace elements of very large sparse matrices over small finite fields. The heuristic currently in use, namely, Montgomery's method [10], is unreliable for certain input matrices. This paper introduces a new biconditional block Lanczos approach based on lookahead, a technique designed to improve the reliability of the scalar Lanczos algorithm. Empirical data show that the performance of the lookahead-based algorithm is competitive with that of Montgomery's heuristic when their relative reliability is taken into account. The reliability of this new algorithm for arbitrary matrices over small finite fields is then established. In the process, some results on the ranks of certain submatrices of a randomly determined block Hankel matrix are established. These results may be applicable in other contexts, such as Coppersmith's block Wiedemann algorithm [3].

Krylov-based algorithms have recently been used, in combination with other methods, to solve systems of linear equations and to perform related matrix computations over finite fields. For example, large and sparse systems of linear equations ;2; are formed during the use of the number field sieve for integer factorization, and elements of the null space of these systems are sampled.Two rather different kinds of block algorithms have recently been considered. Block Wiedemann algorithms have now been presented and fully analyzed. Block Lanczos algorithms were proposed earlier but are not yet as well understood. In particular, proofs of reliability of block Lanczos algorithms are not yet available. Nevertheless, an examination of the computational number theory literature suggests that block Lanczos algorithms continue to be preferred.This report presents a block Lanczos algorithm that is somewhat simpler than block algorithms that are presently in use and provably reliable for computations over large fields. To my knowledge, this is the first block Lanczos algorithm for which a proof of reliability is available.A different Krylov-based approach is considered for computations over small fields: It is shown that if Wiedemann's sparse matrix preconditioner is applied to an arbitrary matrix then the number of nontrivial invariant factors of the result is, with high probability, quite small. A Krylov-based algorithm to compute a partial Frobenius decomposition can then be used to sample from the null space of the original matrix or to compute its rank. This yields a randomized (Monte Carlo) black box algorithm for matrix rank that is asymptotically faster, in the small field case, than any other that is presently known.

Krylov-based algorithms have recently been used (alone, or in combination with other methods) in order to solve systems of linear equations that arise during integer factorization and discrete logarithm computations. Since these include systems over small finite fields, the behaviour of these algorithms in this setting is of interest.Unfortunately, the application of these methods is complicated by the possibility of several kinds of breakdown. Orthogonal vectors can arise when a variant of the Lanczos algorithm is used to generate a basis, and zero-discrepancies can arise during the computation of minimal polynomials of linearly recurrent sequences when Wiedemann's algorithm is applied.Several years ago, Austin Lobo reported experimental evidence that zero-discrepancies are extremely unlikely when a randomized version of Wiedemann's algorithm is applied to solve systems over large fields. With high probability, results are correct if a computation is terminated as soon as such a sequence is detected. "Early termination" has consequently been included in recent implementations.In this paper, we analyze the probability of long sequences of zero-discrepancies during computations of minimal polynomials of the linearly recurrent sequences that arise when simple Krylov-based algorithms are used to solve systems over very small finite fields. Variations of these algorithms that incorporate early termination are briefly presented and analyzed in the small field case.

A probabilistic algorithm is presented to find the determinant of a nonsingular, integer matrix. For a matrix A/spl isin/Z/sup n/spl times/n/ the algorithm requires O(n/sup 3.5/(log n)/sup 4.5/) bit operations (assuming for now that entries in A have constant size) using standard matrix and integer arithmetic. Using asymptotically fast matrix arithmetic, a variant is described which requires O(n/sup 2+/spl theta//2//spl middot/log/sup 2/nloglogn) bit operations, where n/spl times/n matrices can be multiplied with O(n/sup /spl theta//) operations. The determinant is found by computing the Smith form of the integer matrix an extremely useful canonical form in itself. Our algorithm is probabilistic of the Monte Carlo type. That is, it assumes a source of random bits and on any invocation of the algorithm there is a small probability of error.

A new randomized algorithm is presented for computation of the Frobenius form and transition matrix for an n × n matrix over a field. Using standard matrix and polynomial arithmetic, the algorithm has an asymptotic expected complexity that matches the worst case complexity of the best known deterministic algorithmic for this problem, recently given by Storjohann and Villard [16]. The new algorithm is based on the evaluation of Krylov spaces, rather than an climination technique, and may therefore be superior when applied to sparse or structured matrices with a small number of invariant factors.

Las Vegas algorithms that are based on Lanczos's method for solving symmetric linear systems are presented and analyzed. These are compared to a similar randomized Lanczos algorithm that has been used for integer factorization, and to the (provably reliable) algorithm of Wiedemann. The analysis suggests that our Lanczos algorithms are preferable to several versions of Wiedemann's method for computations over large fields, especially for certain symmetric matrix computations. 1 Introduction Sparse or structured systems of linear equations over fields arise in a variety of applications; for example, many methods for integer factorization require the solutions of large, sparse systems over finite fields. Several algorithms have been proposed for this computation over the years. Until recently, the algorithm of Wiedemann [15] was the only such algorithm known to be provably efficient and reliable for computations for arbitrary fields --- particularly, over small finite fields. However, o...

We present new, efficient algorithms for some fundamental computations with finite-dimensional (but not necessarily commutative)associative algebras.For a semisimple associative algebra ~over a finite field or number field F, we show how to compute a basis for the centre of X and the complete Wedderburn decomposition of 2! as a direct sum of simple algebras.If ~is given by a generating set of matrices in F~xm then our algorithm requires about 0(rn3) operations in F, plus the cost of factoring a polynomial in F[z] of degree O(m), and the cost of generating a small number of random elements from fl.We also show how to compute a complete set of orthogonal primitive idempotents in any associative algebra over a finite field.

Some tradeoffs between the size and depth of algebraic formulas are shown. In particular, it is shown that, for any fixed $\epsilon > 0$, any algebraic formula of size S can be converted into an equivalent formula of depth $O(\log S)$ and size $O(S^{1+\epsilon})$. This result is an improvement over previously known results where, to obtain the same depth bound, the formula size is $\Omega (S^{\alpha})$ with $\alpha \geq 2$.

An efficient parallel Las Vegas algorithm is presented for computation of the determinant of a non-singular band matrix and for the solution of a system of linear equations with a band matrix as coefficient matrix. The algorithm can be implemented using time polylogarithmic in n with O(nm/sup omega -1/) processors, in order to process an input matrix with order n and band width m, provided that n*n matrices can be multiplied in logarithmic time with O(n/sup omega /) processors. If asymptotically efficient matrix multiplication is used ( omega>

Some tradeoffs between the size and depth of algebraic formulas are proved. It is shown that, for any fixed in >0, any algebraic formula of size S can be converted into an equivalent formula of depth O(log S) and size O(S/sup 1+ in /). This result is an improvement over previously known results where, to obtain the same depth bound, the formula size is Omega (S/sup alpha /), with alpha >or=2.>

Parallel algorithms for polynomial arithmetic—multiplication of n polynomials of degree m, polynomial division with remainder, and polynomial interpolation—are presented. These algorithms can be implemented using polynomial time constructible families of Boolean circuits of polynomial size and optimal order depth, or log space constructible families of polynomial size and near optimal depth, for computations over $\mathbb{Z},\mathbb{Q}$, finite fields, and several other domains. Arithmetic circuits of polynomial size and optimal order depth are obtained for polynomial arithmetic over arbitrary fields.

We present very efficient arithmetic circuits for the computation of the determinants and inverse of band matrices and for interpolation and polynomial arithmetic over arbitrary ground fields. For input size n the circuits for band matrix inversion (for constant band width) over infinite fields, and the circuits for polynomial arithmetic over arbitrary fields, have optimal depth 0(log n) and polynomial size. The algorithm for band matrix inversion is based on an extension of the method of modification (from numerical analysis) which includes a formula for the determinant of a modified matrix.