Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections (2007)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
Block projections have been used, in [Eberly et al. 2006], to obtain an efficient algorithm to find solutions for sparse systems of linear equations. A bound of softO(n^(2.5)) machine operations is...
Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections (2007)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
Block projections have been used, in [Eberly et al. 2006], to obtain an efficient algorithm to find solutions for sparse systems of linear equations. A bound of softO(n^(2.5)) machine operations is...
Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections (2007)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
Block projections have been used, in [Eberly et al. 2006], to obtain an efficient algorithm to find solutions for sparse systems of linear equations. A bound of softO(n^(2.5)) machine operations is...
Solving Sparse Integer Linear Systems (2006)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
We propose a new algorithm to solve sparse linear systems of equations over the integers. This algorithm is based on a $p$-adic lifting technique combined with the use of block matrices with...
Solving Sparse Integer Linear Systems (2006)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
We propose a new algorithm to solve sparse linear systems of equations over the integers. This algorithm is based on a $p$-adic lifting technique combined with the use of block matrices with...
Solving Sparse Integer Linear Systems (2006)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
We propose a new algorithm to solve sparse linear systems of equations over the integers. This algorithm is based on a $p$-adic lifting technique combined with the use of block matrices with...
Solving Sparse Integer Linear Systems (2006)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
We propose a new algorithm to solve sparse linear systems of equations over the integers. This algorithm is based on a $p$-adic lifting technique combined with the use of block matrices with...
Solving Sparse Integer Linear Systems (2006)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
We propose a new algorithm to solve sparse linear systems of equations over the integers. This algorithm is based on a $p$-adic lifting technique combined with the use of block matrices with...
Reliable Krylov-based Algorithms for Matrix Null Space (2004)
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,...
Reliable Krylov-based Algorithms for Matrix Null Space (2004)
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,...
Early Terminiation over Small Fields (2003)
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...
Early Terminiation over Small Fields (2003)
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...
Efficient Matrix Preconditioners for Black Box Linear Algebra (2002)
Li Chen, Wayne Eberly, Erich Kaltofen, B. David Saunders, William J. Turner
The main idea of the "black box" approach in exact linear algebra is to reduce matrix problems to the computation of minimum polynomials. In most cases preconditioning is necessary to obtain the...
Efficient Matrix Preconditioners for Black Box Linear Algebra (2001)
Li Chen, Wayne Eberly, Erich Kaltofen, B. David Saunders, William J. Turner, Gilles Villard
The main idea of the "black box" approach in exact linear algebra is to reduce matrix problems to the computation of minimum polynomials. In most cases preconditioning is necessary to obtain the...
On Computing the Determinant and Smith Form of an Integer Matrix (2000)
Wayne Eberly, Mark Giesbrecht, Gilles Villard
A probabilistic algorithm is presented to find the determinant of a nonsingular, integer matrix. For a matrix A 2 Z nn the algorithm requires O(n 3:5 (logn) 4:5 ) bit operations (assuming for now...
On Computing the Determinant and Smith Form of an Integer Matrix (2000)
Wayne Eberly, Mark Giesbrecht, Gilles Villard
A probabilistic algorithm is presented to find the determinant of a nonsingular, integer matrix. For a matrix A n n the algorithm requires O n 3 5 logn 4 5 bit operations (assuming for now that...
Asymptotically Efficient Algorithms for the Frobenius Form (2000)
A new randomized algorithm is presented for computation of the Frobenius form of an nn matrix over a eld. A version of the algorithm is presented that uses standard arithmetic whose asymptotic...
ASYMPTOTICALLY EFFICIENT ALGORITHMS FOR THE FROBENIUS FORM (2000)
A new randomized algorithm is presented for computation of the Frobenius form of an n x n matrix over a field. A version of the algorithm is presented that uses standard arithmetic whose asymptotic...
ASYMPTOTICALLY EFFICIENT ALGORITHMS FOR THE FROBENIUS FORM (2000)
A new randomized algorithm is presented for computation of the Frobenius form of an n x n matrix over a field. A version of the algorithm is presented that uses standard arithmetic whose asymptotic...
Decompositions of Algebras over ... (2000)
We consider the boolean complexity of the decomposition of matrix algebras over C and R with bases consisting of matrices over a number field. Deterministic polynomial time algorithms for the...
Decomposition Of Algebras Over Finite Fields And Number Fields (2000)
We consider the boolean complexity of the decomposition of semi-simple algebras over finite fields and number fields.
Size-Depth Tradeoffs for Algebraic Formulas (2000)
Nader H. Bshouty, Richard Cleve, Wayne Eberly
Some tradeos between the size and depth of algebraic formulas are shown. In particular, it is shown that, for any xed > 0, any algebraic formula of size S can be converted into an equivalent formula...
On Randomized Lanczos Algorithms (2000)
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...
Efficient Parallel Independent Subsets and Matrix Factorizations (1999)
A parallel algorithm is given for computation of a maximal linearly independent subset of a set of vectors over a field. The algorithm uses polylogarithmic time and uses a number of processors that...
Size-Depth Tradeoffs for Algebraic Formulae (1997)
Nader H. Bshouty, Richard Cleve, Wayne Eberly
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed ffl ? 0, any algebraic formula of size S can be converted into an equivalent...
On Randomized Lanczos Algorithms (1997)
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...
On Randomized Lanczos Algorithms (1997)
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...
On Randomized Lanczos Algorithms (1997)
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...
On Randomized Lanczos Algorithms (1997)
Las Vegas algorithms that are based on Lanczos' method for solving symmetric linear systems are presented and analyzed. These are compared to a similar randomized Lanczos algorithm that has been used...
Efficient Parallel Computations for Singular Band Matrices (1996)
. Efficient parallel algorithms are presented for singular band matrix computations over arbitrary fields --- including solving systems of linear equations, and computation of the rank and a maximal...
SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE (1992)
Eberly, Wayne, Cleve, Richard, Bshouty, Nader H.
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an...
SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE (1992)
Eberly, Wayne, Cleve, Richard, Bshouty, Nader H.
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an...
SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE (1992)
Eberly, Wayne, Cleve, Richard, Bshouty, Nader H.
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an...
SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE (1992)
Eberly, Wayne, Cleve, Richard, Bshouty, Nader H.
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an...
SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE (1992)
Eberly, Wayne, Cleve, Richard, Bshouty, Nader H.
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an...
SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE (1992)
Eberly, Wayne, Cleve, Richard, Bshouty, Nader H.
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an...
EFFICIENT ALGORITHMS FOR THE DECOMPOSITION OF MATRIX ALGEBRAS (1990)
We consider the bit-complexity of the decomposition of semi-simple algebras over finite fields and number fields, and of simple algebras over C and R, for matrix algebras with bases consisting of...
FAST PARALLEL BAND MATRIX ARITHMETIC (1990)
We present parallel algorithms for computation of the determinant, adjoint, characteristic polynomial and rank of band matrices, and for the solution of systems of linear equations with band matrices...
EFFICIENT ALGORITHMS FOR THE DECOMPOSITION OF MATRIX ALGEBRAS (1990)
We consider the bit-complexity of the decomposition of semi-simple algebras over finite fields and number fields, and of simple algebras over C and R, for matrix algebras with bases consisting of...
FAST PARALLEL BAND MATRIX ARITHMETIC (1990)
We present parallel algorithms for computation of the determinant, adjoint, characteristic polynomial and rank of band matrices, and for the solution of systems of linear equations with band matrices...
LOGARITHMIC DEPTH CIRCUITS FOR HERMITE INTERPOLATION (1990)
We present a new parallel algorithm for Hermite interpolation. The algorithm can be implemented using arithmetic-boolean circuits of depth logarithmic and size polynomial in the input size. A...
LOGARITHMIC DEPTH CIRCUITS FOR HERMITE INTERPOLATION (1990)
We present a new parallel algorithm for Hermite interpolation. The algorithm can be implemented using arithmetic-boolean circuits of depth logarithmic and size polynomial in the input size. A...
Thesis (Ph. D.)--University of Toronto, 1989.
Efficient Computations of Frobenius Forms over Small Fields (1970)
A new randomized algorithm is presented for computation of the Frobenius form of an nn matrix over a eld. A version of the algorithm is presented that uses standard arithmetic whose asymptotic...