J-G. Dumas, B. D. Saunders, and G. Villard, Integer Smith Form via the Valence: Experience with Large Sparse Matrices from Homology (gzipped postscript), ISSAC '00, August 6-9, 2000.
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.
M. W. Giesbrecht and B. D. Saunders, Solving Parametric Linear Systems (abstract) ILAS '98, June 3-6, 1998.
M. Giesbrecht, A. Lobo, and B. D. Saunders, Certifying Inconsistency of Sparse Linear Systems (postscript) ISSAC '98, August 13-15, 1998.
Randomized black box algorithms provide a very efficient means for solving sparse linear systems over arbitrary fields. 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 an efficient algorithm to compute a certificate of inconsistency for a black box linear system over a field. The cost of producing such a certificate is shown to be about the same as that of solving the system in the black box model, while the cost of applying a given certificate to prove inconsistency is much smaller. We also give an efficient algorithm for certifying that a sparse Diophantine linear system of integer equations has no integer solutions, even when it may have rational solutions.
Lakshman and Saunders, Sparse Shifts for Univariate Polynomials, Journal of AAECC.
Let f(x) be a polynomial of degree d with rational coefficients and let t be a positive integer no greater than deg(f). We consider the problem of finding a t-sparse shift for f(x). The problem is to find an alpha, if one exists (in some algebraic extension of the rationals), such that in the representation of f(x) in the basis 1, x-alpha, (x-alpha)^2, ..., at most t of the coefficients f_i are non-zero. We derive explicit conditions for the uniqueness and rationality of a t-sparse shift for f(x) and provide an efficient algorithm for computing a sparse shift when one exists. We also point out an application of our result to the problem of constructing sparse decompositions of univariate polynomials.
Lakshman and Saunders, Sparse Polynomial Interpolation in Non-standard Bases, SICOMP (SIAM Journal on Computing), April 1995...
We consider the problem of interpolating univariate polynomials over a field of characteristic zero 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.
Hong R. Lee and B. David Saunders, Fraction Free Gaussian Elimination for Sparse Matrices JSC, Vol. 19, 393-402, 1995.
A variant of the fraction free form of Gaussian elimination is presented. This algorithm reduces the amount of arithmetic involved when the matrix has many zero entries. The advantage can be great for matrices with symbolic entries (integers, polynomials, expressions in trigonometric functions, etc.). %With an appropriate representation of the sparse matrix, %there can even be some advantage when the entries are floating point or from %a finite field. These claims are supported with some analysis and experimental data.
This paper presents empirical data, on a network of workstations, for several parallel implementations of Karatsuba's algorithm for integer multiplication. Algorithms were implemented using Sugarbush, a parallel version of the Maple computer algebra system, which uses C/Linda for parallel operations. The Sugarbush programs were also compared to various programs written directly in C/Linda. Timings are provided for a network of 27 workstations.
Douglas Wiedemann's landmark approach to solving sparse linear systems over finite fields provides the symbolic counterpart to non-combinatorial numerical methods for solving sparse linear systems, such as the Lanczos or conjugate gradient method. The problem is to solve a sparse linear system, when the individual entries lie in a generic field, and the only operations possible are field arithmetic; the solution is to be exact. Such is the situation, for instance, if one works in a finite field.
We contribute to Wiedemann's approach in several ways. For singular systems, we show how to randomly sample from the solution manifold by randomly perturbing the entire system and then solving a non-singular one. Our method is a purely algebraic one, while Wiedemann uses padding with random sparse rows to enforce non-singularity. When computing the rank or determinant of a matrix, one requires left and right multiplier matrices such that the product with the coefficient matrix has a maximal non-zero minor in the left upper corner. We present an alternate to Wiedemann's perturbation that requires asymptotically fewer field elements and is again based on algebraic rather than combinatorical properties. As it turns out, the multipliers can be chosen unit triangular Toeplitz matrices. Furthermore, we present in greater detail a method based on p-adic lifting for solving a sparse system over the rationals.
An adaptive run time scheduling approach to parallel algebraic computation is suggested. Study of a toy example, the factorial function, illustrates the need for such an approach on an asynchronous multiprocessing system. The example is run in several parallelized variants on two distinct implementations of ALDES/SAC2 on a Sequent Symmetry computer.
S. Agnarsson, A. Kandri Rody, D. Kapur, P. Narendran, and B. D. Saunders, Complexity of Testing Whether a Polynomial Ideal is Nontrivial, Proceedings of the 1984 MACSYMA Users Conference, 1984, 452-458.
B. E. Cain, B. D. Saunders, and Hans Schneider, On the Geometry of Dual Pairs, Studies in Appl. Math., Vol. 56, 71-79, 1977.
B. D. Saunders, Matrix Computations in Computer Algebra Systems, U. of Delaware Center for Mathematical Computation Technical Report CMC-8808.
E. Kaltofen, M. Krishnamoorthy, and B. D. Saunders, Randomized Parallel Computation of the Smith Normal Form of Polynomial Matrices, U. of Delaware Center for Mathematical Computation Technical Report CMC-8702 (superceded by subsequent publication).