Abstract: Montgomery's block Lanczos algorithm is a blocked extension to the scalar Lanczos iteration for solving linear systems over finite fields. It facilitates parallelization and allegedly improves the probability of success over small finite fields. This talk examines the algorithm on theoretical and empirical levels, examining how the probability of success depends on the blocking factor and the characteristics of the input matrix.
Abstract: The classical and intensively studied problem of solving a Toeplitz/Hankel linear system of equations is omnipresent in computations in sciences, engineering and signal processing. We study this subject as a computer algebra problem assuming a nonsingular integer input and rely on Hensel's $p$-adic lifting to improve the current fastest divide-and-conquer algorithm by Morf 1974/1980 and Bitmead and Anderson 1980. With randomization, lifting enables solution of a nonsingular Toeplitz/Hankel linear system of $n$ equations by using $O(m(n) n\mu(\log n))$ bit operations (versus the information lower bound of $n2\log n$), where $m(n)$ and $\mu(d)$ bound the arithmetic and Boolean cost of multiplying polynomials of degree $n$ and integers modulo $2^d+1$, respectively, and the input coefficients are integers in $n^{O(1)}$. Furthermore, we extend our algorithms and cost bound to $q$-adic lifting for a fixed integer $q$, in particular $q=2^g$ allowing computations in binary form. This enhances practical value of our study. In Pan 2002 \cite{pa} the algorithms and the bit cost estimates are extended to solving nonsingular and consistent singular Toeplitz/Hankel-like linear systems and computing the rank and a vector from or a basis for the null space of a Toeplitz/Hankel-like matrix as well as the resultant, gcd and lcm of two polynomials of bounded degrees, a fixed entry of a Pad\'e approximation table, and the Berlekamp-Massey linear recurrence coefficients provided that the input values are some bounded integers. To yield this extension, Hensel's lifting is combined with the Morf-Bitmead-Anderson's divide-and-conquer algorithm, where again we allow computations both modulo a random prime and a fixed prime power, in particular a power of 2.
Abstract: Iterative methods for solving linear systems are based on Krylov subspaces generated by a fixed linear mapping and a set of elements in a vector space. We consider the probability that a random Krylov subspace in a vector space over a finite field equals the whole space itself. We present an exact formula for this probability, and from it we derive good lower bounds that approach 1 exponentially fast as the size of the set increases.
Joint work with Richard P. Brent and Alan G. B. Lauder.
Abstract: Block Lanczos algorithms have recently been used to sample from the nullspace of sparse matrices over small fields, as part of number-theoretic computations. While experimental evidence suggests that these computations are reliable, considerable work remains to be done in order to prove that this is generally the case.
This talk includes prelimary work to investigate the worst-case expected behaviour of randomized versions of a block Lanczos algorithm to sample from the nullspace or estimate the rank of a given matrix, and to determine the consistency of a given sparse system of equations.
In particular, it will be shown that these methods are provably unreliable in the worst case, when they are applied to solve problems that include sparse matrices over small fields, unless the input matrix is also conditioned in some way. A sparse conditioner that addresses the problems, suggested above, will also be proposed.
Abstract: Numerical libraries provide fast routines for floating point arithmetic. We know that using such libraries allows for faster matrix mutliplication over finite fields. In particular, there exists a fast matrix multiplication routine based on BLAS. Using this work, we go further by providing fast routines for solving basic exact linear algebra problems such as LSP factorization and triangular system solving. In this talk we describe these routines and their application to computing the minimal matrix polynomial. More generally, these routines should be useful for other algorithms that incorporate matrix multiplication. This work is part of the LinBox project. (See http://www.linalg.org).
Abstract: We present an iterative refinement method based on a linear Newton iteration for solving a particular group of high precision computation problems. Our method generates an initial solution at hardware floating point precision using a traditional method and then repeatedly refines this solution to higher precision, exploiting hardware floating point computation in each iteration. This is in contrast to direct solution of the high precision problem completely in software floating point. Theoretical cost analysis, as well as experimental evidence, shows a significant reduction in computational cost is achieved by the iterative refinement method on this group of problems.
Abstract: The Bezout-Cayley-Dixon resultant is a useful and efficient way to solve systems of polynomial equations. This has been known since at least the 1994 paper by Kapur, Saxena, and Yang [KSY]. Their key idea was proven correct in great generality by the 2000 paper of Buse, Elkadi, and Mourrain [BEM]. I will summarize some of the large problems I have solved with it, in which it has routinely bested Groebner basis techniques by several orders of magnitude.
I will discuss:
[KSY] D. Kapur, T. Saxena, and L. Yang, Algebraic and geometric reasoning using Dixon resultants. In: Proc. of the International Symposium on Symbolic and Algebraic Computation. A.C.M. Press (1994).
Abstract: Blackbox algorithms for sparse and structured matrices have proven very effective and are the core of LinBox. In this talk, we consider matrices in which the storage of matrix elements is a small multiple of the matrix dimension. Blackbox methods are particularly useful in this situation, especially for large problems where memory is at a premium. However, Gaussian elimination based methods are generally faster for small matrices and cases where fill-in is sufficiently low. It is hard to predict a priori which method will be best for many matrices. We discuss topics related to the design of hybrid algorithms that adapt to the properties of the matrix at hand.
Saunders will discuss the situation for matrices with just 2 nonzero elements per row and mention some situations in which these arise. In this situation, fill-in may be avoided but elimination must be done with care for optimal performance.
Wan will describe a hybrid of sparse elimination, SuperLU, and Wiedemann's blackbox approach. Included will be a report on the latest optimization of field arithmetic in prime fields for these algorithms.
Lobo will report on the status of implementation of blackboxes for Toeplitz and other structured matrices using fast, FFT based, polynomial arithmetic. Comparisons showing the cutoff threshold between this and dense matrix elimination will be presented.
Abstract: The effectiveness of adapting highly optimized numerical BLAS routines to the task of exact matrix multiplication over finite fields has been established by project F.F.L.A.S. (Finite field linear algebra subroutines) from Dumas, Pernet, Brassel, and Gautier. Some of the ideas from that project, in particular a fast matrix multiplication algorithm for small prime fields, are now incorporated into the Maple computer algebra system.
In this talk we describe a Maple implementation of an algorithm for computing the echelon transform. This single routine gives effective reductions to matrix multiplication for many other tasks, such as computation of rank, rank profile, determinant, inverse, nullspace, and solution of a linear system. To evaluate our implementation we use a ratio test, e.g. we plot the ratio of time taken to compute the determinant of an $n \times n$ matrix and the time taken to multiply two $n \times n$ matrices. The goal is a ratio of less than one. Joint work with Zhuliang Chen.