The Experts below are selected from a list of 22479 Experts worldwide ranked by ideXlab platform

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, 2020
    Co-Authors: Stavros Birmpilis, George Labahn, Arne Storjohann
    Abstract:

    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.

  • deterministic reduction of Integer nonsingular linear system solving to Matrix multiplication
    International Symposium on Symbolic and Algebraic Computation, 2019
    Co-Authors: Stavros Birmpilis, George Labahn, Arne Storjohann
    Abstract:

    We present a deterministic reduction to Matrix multiplication for the problem of linear system solving: given as input a nonsingular A \in \Z^n \times n and b \in \Z^n \times 1 , compute A^-1 b. We give an algorithm that computes the minimal Integer e such that all denominators of the entries in 2^eA^-1 are relatively prime to 2. Then, for a b that has entries with bitlength O(n) times as large as the bitlength of entries in A, we give an algorithm to produce the 2-adic expansion of 2^eA^-1 b up to a precision high enough such that A^-1 b over \Q can be recovered using rational number reconstruction. Both e and the 2-adic expansion can be computed in O(\MM(n,log n + log ||A||) \times (log n) (log n + loglog ||A||)) bit operations. Here, ||A||= \max_ij |A_ij | and \MM(n,d) is the cost to multiply together, modulo 2^d, two n \times n Integer matrices. Our approach is based on the previously known reductions of linear system solving to Matrix multiplication which use randomization to find an Integer lifting modulus X that is relatively prime to \det A. Here, we derandomize by first computing a permutation P, a unit upper triangular M, and a diagonal S with \det S a power of two, such that U := APMS^-1 is an Integer Matrix with 2 \perp \det U. This allows our modulus X to be chosen a power of 2.

  • On the complexity of inverting Integer and polynomial matrices
    computational complexity, 2015
    Co-Authors: Arne Storjohann
    Abstract:

    An algorithm is presented that probabilistically computes the exact inverse of a nonsingular n × n Integer Matrix A using $${({n^3(\log||A||+\log \kappa(A)))}^{1+o(1)}}$$ ( n 3 ( log | | A | | + log κ ( A ) ) ) 1 + o ( 1 ) bit operations. Here, $${||A||= \max_{ij}|A_{ij}|}$$ | | A | | = max i j | A i j | denotes the largest entry in absolute value, $${\kappa(A) := n ||A^{-1}||\,||A||}$$ κ ( A ) : = n | | A - 1 | | | | A | | is the condition number of the input Matrix, and the “+ o (1)” in the exponent indicates a missing factor $${c_1 {(\log n)}^{c_2}{({\rm loglog} ||A||)}^{c_3}}$$ c 1 ( log n ) c 2 ( loglog | | A | | ) c 3 for positive real constants c _1, c _2, c _3. A variation of the algorithm is presented for polynomial matrices that computes the inverse of a nonsingular n × n Matrix whose entries are polynomials of degree d over a field using $${{(n^3d)}^{1+o(1)}}$$ ( n 3 d ) 1 + o ( 1 ) field operations. Both algorithms are randomized of the Las Vegas type: failure may be reported with probability at most 1/2, and if failure is not reported, then the output is certified to be correct in the same running time bound.

  • Consider a 2n × 2n Integer Matrix
    2015
    Co-Authors: Arne Storjohann
    Abstract:

    be a 2n × 2n Integer Matrix with the prin-cipal block A square and nonsingular. An algorithm is pre-sented to determine if the Schur complement D−CA−1B is equal to the zero Matrix in O (̃nω log ||M ||) bit operations. Here, ω is the exponent of Matrix multiplication and ||M || denotes the largest entry in absolute value. The algorithm is randomized of the Las Vegas type, and either returns the correct answer (“yes ” or “no”), or returns fail with proba-bility less than 1/2. This gives a Las Vegas algorithm for computing the rank r of an n ×m Integer Matrix A in a

  • faster inversion and other black box Matrix computations using efficient block projections
    International Symposium on Symbolic and Algebraic Computation, 2007
    Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles Villard
    Abstract:

    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.

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, 2007
    Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles Villard
    Abstract:

    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
    2007
    Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles Villard
    Abstract:

    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, 2002
    Co-Authors: Mark Giesbrecht
    Abstract:

    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, 1996
    Co-Authors: Mark Giesbrecht
    Abstract:

    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.

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, 2007
    Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles Villard
    Abstract:

    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
    2007
    Co-Authors: Wayne Eberly, Mark Giesbrecht, Arne Storjohann, Pascal Giorgi, Gilles Villard
    Abstract:

    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.

Stavros Birmpilis - 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, 2020
    Co-Authors: Stavros Birmpilis, George Labahn, Arne Storjohann
    Abstract:

    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.

  • deterministic reduction of Integer nonsingular linear system solving to Matrix multiplication
    International Symposium on Symbolic and Algebraic Computation, 2019
    Co-Authors: Stavros Birmpilis, George Labahn, Arne Storjohann
    Abstract:

    We present a deterministic reduction to Matrix multiplication for the problem of linear system solving: given as input a nonsingular A \in \Z^n \times n and b \in \Z^n \times 1 , compute A^-1 b. We give an algorithm that computes the minimal Integer e such that all denominators of the entries in 2^eA^-1 are relatively prime to 2. Then, for a b that has entries with bitlength O(n) times as large as the bitlength of entries in A, we give an algorithm to produce the 2-adic expansion of 2^eA^-1 b up to a precision high enough such that A^-1 b over \Q can be recovered using rational number reconstruction. Both e and the 2-adic expansion can be computed in O(\MM(n,log n + log ||A||) \times (log n) (log n + loglog ||A||)) bit operations. Here, ||A||= \max_ij |A_ij | and \MM(n,d) is the cost to multiply together, modulo 2^d, two n \times n Integer matrices. Our approach is based on the previously known reductions of linear system solving to Matrix multiplication which use randomization to find an Integer lifting modulus X that is relatively prime to \det A. Here, we derandomize by first computing a permutation P, a unit upper triangular M, and a diagonal S with \det S a power of two, such that U := APMS^-1 is an Integer Matrix with 2 \perp \det U. This allows our modulus X to be chosen a power of 2.

Sergei Konyagin - One of the best experts on this subject based on the ideXlab platform.

  • an extremal problem for Integer sparse recovery
    Linear Algebra and its Applications, 2020
    Co-Authors: Sergei Konyagin, Benny Sudakov
    Abstract:

    Abstract Motivated by the problem of Integer sparse recovery we study the following question. Let A be an m × d Integer Matrix whose entries are in absolute value at most k. How large can be d = d ( m , k ) if all m × m submatrices of A are non-degenerate? We obtain new upper and lower bounds on d and answer a special case of the problem by Brass, Moser and Pach on covering m-dimensional k × ⋯ × k grid by linear subspaces.

  • an extremal problem for Integer sparse recovery
    arXiv: Combinatorics, 2019
    Co-Authors: Sergei Konyagin, Benny Sudakov
    Abstract:

    Motivated by the problem of Integer sparse recovery we study the following question. Let $A$ be an $m \times d$ Integer Matrix whose entries are in absolute value at most $k$. How large can be $d=d(m,k)$ if all $m \times m$ submatrices of $A$ are non-degenerate? We obtain new upper and lower bounds on $d$ and answer a special case of the problem by Brass, Moser and Pach on covering $m$-dimensional $k \times \cdots\times k$ grid by linear subspaces.

  • on the recovery of an Integer vector from linear measurements
    Mathematical Notes, 2018
    Co-Authors: Sergei Konyagin
    Abstract:

    Let 1 ≤ 2l ≤ m < d. A vector x ∈ ℤd is said to be l-sparse if it has at most l nonzero coordinates. Let an m × d Matrix A be given. The problem of the recovery of an l-sparse vector x ∈ Zd from the vector y = Ax ∈ Rm is considered. In the case m = 2l, we obtain necessary conditions and sufficient conditions on the numbers m, d, and k ensuring the existence of an Integer Matrix A all of whose elements do not exceed k in absolute value which makes it possible to reconstruct l-sparse vectors in ℤd. For a fixed m, these conditions on d differ only by a logarithmic factor depending on k.