The Experts below are selected from a list of 24846 Experts worldwide ranked by ideXlab platform
Mark Giesbrecht - One of the best experts on this subject based on the ideXlab platform.
-
faster inversion and other black box matrix computations using efficient block projections
International Symposium on Symbolic and Algebraic Computation, 2007Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles VillardAbstract: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. In this paper we establish the correctness of the algorithm from [10] by proving the existence of efficient block projections for arbitrary non-singular matrices over sufficiently large fields. We further demonstrate the usefulness of these projections by incorporating them into existing black-box matrix algorithms to derive improved bounds for the cost of several matrix problems. We consider, in particular, matrices that can be multiplied by a vector using O~(n) field operations: We show how to compute the inverse of any such non-singular matrix over any field using an expected number of O~(n2.27) operations in that field. A basis for the null space of such a matrix, and a certification of its rank, are obtained at the same cost. An application of this technique to Kaltofen and Villard's Baby-Steps/Giant-Steps algorithms for the determinant and Smith Form of an integer matrix is also sketched, yielding algorithms requiring O~(n2.66) machine operations. More general bounds involving the number of black-box matrix operations to be used are also obtained. The derived algorithms are all probabilistic of the Las Vegas type. They are assumed to be able to generate random elements - bits or field elements - at unit cost, and always output the correct answer in the expected time given.
-
Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections
2007Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles VillardAbstract: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 obtained assuming that the input matrix can be multiplied by a vector with constant-sized entries in softO(n) machine operations. Unfortunately, the correctness of this algorithm depends on the existence of efficient block projections, and this has been conjectured. In this paper we establish the correctness of the algorithm from [Eberly et al. 2006] by proving the existence of efficient block projections over sufficiently large fields. We demonstrate the usefulness of these projections by deriving improved bounds for the cost of several matrix problems, considering, in particular, ``sparse'' matrices that can be be multiplied by a vector using softO(n) field operations. We show how to compute the inverse of a sparse matrix over a field F using an expected number of softO(n^(2.27)) operations in F. A basis for the null space of a sparse matrix, and a certification of its rank, are obtained at the same cost. An application to Kaltofen and Villard's Baby-Steps/Giant-Steps algorithms for the determinant and Smith Form of an integer matrix yields algorithms requiring softO(n^(2.66)) machine operations. The derived algorithms are all probabilistic of the Las Vegas type.
-
fast computation of the Smith Form of a sparse integer matrix
Computational Complexity, 2002Co-Authors: Mark GiesbrechtAbstract:We present a new probabilistic algorithm to compute the Smith normal Form of a sparse integer matrix \( A \in {\Bbb Z}^{m \times n} \). The algorithm treats A as a “black box”—A is only used to compute matrix-vector products and we do not access individual entries in A directly. The algorithm requires about \( O(m^2 {\rm log} \parallel A \parallel) \) black box evaluations \( w \mapsto Aw\,{\rm mod}\,p \) for word-sized primes p and \( w \in {\Bbb Z}^{n \times 1}_p \), plus \( O(m^2 n\,{\rm log} \parallel A \parallel +\,m^3\,{\rm log^2} \parallel A \parallel) \) additional bit operations. For sparse matrices this represents a substantial improvement over previously known algorithms. The new algorithm suffers from no “fill-in” or intermediate value explosion, and uses very little additional space. We also present an asymptotically fast algorithm for dense matrices which requires about \( O(n \cdot {\rm MM}(m)\,{\rm log} \parallel A \parallel +\,m^3\,{\rm log^2} \parallel A \parallel) \) bit operations, where O(MM(m)) operations are sufficient to multiply two \( m \times m \) matrices over a field. Both algorithms are probabilistic of the Monte Carlo type — on any input they return the correct answer with a controllable, exponentially small probability of error.
-
probabilistic computation of the Smith normal Form of a sparse integer matrix
Algorithmic Number Theory Symposium, 1996Co-Authors: Mark GiesbrechtAbstract:We present a new probabilistic algorithm to compute the Smith normal Form of a sparse integer matrix A ∈ ℤm×n. The algorithm treats A as a “black-box”; A is only used to compute matrix-vector products and we don't access individual entries in A directly. The algorithm requires about O(m2 log ∥A∥) such black-box evaluations reduced modulo word-sized primes p on vectors in ℤ p n×1 , plus O(m2n log ∥A∥) additional bit operations. For sparse matrices this represents a substantial improvement over previously known algorithms. For example, on an n×n integer matrix A with O(n log n) non-zero entries, only about O(n3 log2 ∥A∥) bit operations are required to find the Smith Form using standard integer arithmetic. The new algorithm suffers from no “fill-in” or intermediate value explosion, and uses very little additional space. The algorithm is probabilistic of the Monte Carlo type — on any input it returns the correct answer with a controllable, exponentially small probability of error.
Arne Storjohann - One of the best experts on this subject based on the ideXlab platform.
-
a las vegas algorithm for computing the Smith Form of a nonsingular integer matrix
International Symposium on Symbolic and Algebraic Computation, 2020Co-Authors: Stavros Birmpilis, George Labahn, Arne StorjohannAbstract:We present a Las Vegas randomized algorithm to compute the Smith normal Form of a nonsingular integer matrix. For an A ∈ Zn×n, the algorithm requires O(n3(log n + log ||A||)2 (log n)2) bit operations using standard integer and matrix arithmetic, where ||A|| = maxij |Aij | denotes the largest entry in absolute value. Fast integer and matrix multiplication can also be used, establishing that the Smith Form can be computed in about the same number of bit operations as required to multiply two matrices of the same dimension and size of entries as the input matrix.
-
faster inversion and other black box matrix computations using efficient block projections
International Symposium on Symbolic and Algebraic Computation, 2007Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles VillardAbstract: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. In this paper we establish the correctness of the algorithm from [10] by proving the existence of efficient block projections for arbitrary non-singular matrices over sufficiently large fields. We further demonstrate the usefulness of these projections by incorporating them into existing black-box matrix algorithms to derive improved bounds for the cost of several matrix problems. We consider, in particular, matrices that can be multiplied by a vector using O~(n) field operations: We show how to compute the inverse of any such non-singular matrix over any field using an expected number of O~(n2.27) operations in that field. A basis for the null space of such a matrix, and a certification of its rank, are obtained at the same cost. An application of this technique to Kaltofen and Villard's Baby-Steps/Giant-Steps algorithms for the determinant and Smith Form of an integer matrix is also sketched, yielding algorithms requiring O~(n2.66) machine operations. More general bounds involving the number of black-box matrix operations to be used are also obtained. The derived algorithms are all probabilistic of the Las Vegas type. They are assumed to be able to generate random elements - bits or field elements - at unit cost, and always output the correct answer in the expected time given.
-
Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections
2007Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles VillardAbstract: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 obtained assuming that the input matrix can be multiplied by a vector with constant-sized entries in softO(n) machine operations. Unfortunately, the correctness of this algorithm depends on the existence of efficient block projections, and this has been conjectured. In this paper we establish the correctness of the algorithm from [Eberly et al. 2006] by proving the existence of efficient block projections over sufficiently large fields. We demonstrate the usefulness of these projections by deriving improved bounds for the cost of several matrix problems, considering, in particular, ``sparse'' matrices that can be be multiplied by a vector using softO(n) field operations. We show how to compute the inverse of a sparse matrix over a field F using an expected number of softO(n^(2.27)) operations in F. A basis for the null space of a sparse matrix, and a certification of its rank, are obtained at the same cost. An application to Kaltofen and Villard's Baby-Steps/Giant-Steps algorithms for the determinant and Smith Form of an integer matrix yields algorithms requiring softO(n^(2.66)) machine operations. The derived algorithms are all probabilistic of the Las Vegas type.
Gilles Villard - One of the best experts on this subject based on the ideXlab platform.
-
faster inversion and other black box matrix computations using efficient block projections
International Symposium on Symbolic and Algebraic Computation, 2007Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles VillardAbstract: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. In this paper we establish the correctness of the algorithm from [10] by proving the existence of efficient block projections for arbitrary non-singular matrices over sufficiently large fields. We further demonstrate the usefulness of these projections by incorporating them into existing black-box matrix algorithms to derive improved bounds for the cost of several matrix problems. We consider, in particular, matrices that can be multiplied by a vector using O~(n) field operations: We show how to compute the inverse of any such non-singular matrix over any field using an expected number of O~(n2.27) operations in that field. A basis for the null space of such a matrix, and a certification of its rank, are obtained at the same cost. An application of this technique to Kaltofen and Villard's Baby-Steps/Giant-Steps algorithms for the determinant and Smith Form of an integer matrix is also sketched, yielding algorithms requiring O~(n2.66) machine operations. More general bounds involving the number of black-box matrix operations to be used are also obtained. The derived algorithms are all probabilistic of the Las Vegas type. They are assumed to be able to generate random elements - bits or field elements - at unit cost, and always output the correct answer in the expected time given.
-
Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections
2007Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles VillardAbstract: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 obtained assuming that the input matrix can be multiplied by a vector with constant-sized entries in softO(n) machine operations. Unfortunately, the correctness of this algorithm depends on the existence of efficient block projections, and this has been conjectured. In this paper we establish the correctness of the algorithm from [Eberly et al. 2006] by proving the existence of efficient block projections over sufficiently large fields. We demonstrate the usefulness of these projections by deriving improved bounds for the cost of several matrix problems, considering, in particular, ``sparse'' matrices that can be be multiplied by a vector using softO(n) field operations. We show how to compute the inverse of a sparse matrix over a field F using an expected number of softO(n^(2.27)) operations in F. A basis for the null space of a sparse matrix, and a certification of its rank, are obtained at the same cost. An application to Kaltofen and Villard's Baby-Steps/Giant-Steps algorithms for the determinant and Smith Form of an integer matrix yields algorithms requiring softO(n^(2.66)) machine operations. The derived algorithms are all probabilistic of the Las Vegas type.
Wayne Eberly - One of the best experts on this subject based on the ideXlab platform.
-
faster inversion and other black box matrix computations using efficient block projections
International Symposium on Symbolic and Algebraic Computation, 2007Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles VillardAbstract: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. In this paper we establish the correctness of the algorithm from [10] by proving the existence of efficient block projections for arbitrary non-singular matrices over sufficiently large fields. We further demonstrate the usefulness of these projections by incorporating them into existing black-box matrix algorithms to derive improved bounds for the cost of several matrix problems. We consider, in particular, matrices that can be multiplied by a vector using O~(n) field operations: We show how to compute the inverse of any such non-singular matrix over any field using an expected number of O~(n2.27) operations in that field. A basis for the null space of such a matrix, and a certification of its rank, are obtained at the same cost. An application of this technique to Kaltofen and Villard's Baby-Steps/Giant-Steps algorithms for the determinant and Smith Form of an integer matrix is also sketched, yielding algorithms requiring O~(n2.66) machine operations. More general bounds involving the number of black-box matrix operations to be used are also obtained. The derived algorithms are all probabilistic of the Las Vegas type. They are assumed to be able to generate random elements - bits or field elements - at unit cost, and always output the correct answer in the expected time given.
-
Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections
2007Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles VillardAbstract: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 obtained assuming that the input matrix can be multiplied by a vector with constant-sized entries in softO(n) machine operations. Unfortunately, the correctness of this algorithm depends on the existence of efficient block projections, and this has been conjectured. In this paper we establish the correctness of the algorithm from [Eberly et al. 2006] by proving the existence of efficient block projections over sufficiently large fields. We demonstrate the usefulness of these projections by deriving improved bounds for the cost of several matrix problems, considering, in particular, ``sparse'' matrices that can be be multiplied by a vector using softO(n) field operations. We show how to compute the inverse of a sparse matrix over a field F using an expected number of softO(n^(2.27)) operations in F. A basis for the null space of a sparse matrix, and a certification of its rank, are obtained at the same cost. An application to Kaltofen and Villard's Baby-Steps/Giant-Steps algorithms for the determinant and Smith Form of an integer matrix yields algorithms requiring softO(n^(2.66)) machine operations. The derived algorithms are all probabilistic of the Las Vegas type.
Pascal Giorgi - One of the best experts on this subject based on the ideXlab platform.
-
faster inversion and other black box matrix computations using efficient block projections
International Symposium on Symbolic and Algebraic Computation, 2007Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles VillardAbstract: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. In this paper we establish the correctness of the algorithm from [10] by proving the existence of efficient block projections for arbitrary non-singular matrices over sufficiently large fields. We further demonstrate the usefulness of these projections by incorporating them into existing black-box matrix algorithms to derive improved bounds for the cost of several matrix problems. We consider, in particular, matrices that can be multiplied by a vector using O~(n) field operations: We show how to compute the inverse of any such non-singular matrix over any field using an expected number of O~(n2.27) operations in that field. A basis for the null space of such a matrix, and a certification of its rank, are obtained at the same cost. An application of this technique to Kaltofen and Villard's Baby-Steps/Giant-Steps algorithms for the determinant and Smith Form of an integer matrix is also sketched, yielding algorithms requiring O~(n2.66) machine operations. More general bounds involving the number of black-box matrix operations to be used are also obtained. The derived algorithms are all probabilistic of the Las Vegas type. They are assumed to be able to generate random elements - bits or field elements - at unit cost, and always output the correct answer in the expected time given.
-
Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections
2007Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles VillardAbstract: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 obtained assuming that the input matrix can be multiplied by a vector with constant-sized entries in softO(n) machine operations. Unfortunately, the correctness of this algorithm depends on the existence of efficient block projections, and this has been conjectured. In this paper we establish the correctness of the algorithm from [Eberly et al. 2006] by proving the existence of efficient block projections over sufficiently large fields. We demonstrate the usefulness of these projections by deriving improved bounds for the cost of several matrix problems, considering, in particular, ``sparse'' matrices that can be be multiplied by a vector using softO(n) field operations. We show how to compute the inverse of a sparse matrix over a field F using an expected number of softO(n^(2.27)) operations in F. A basis for the null space of a sparse matrix, and a certification of its rank, are obtained at the same cost. An application to Kaltofen and Villard's Baby-Steps/Giant-Steps algorithms for the determinant and Smith Form of an integer matrix yields algorithms requiring softO(n^(2.66)) machine operations. The derived algorithms are all probabilistic of the Las Vegas type.
