Computing the log-determinant of symmetric, diagonally dominant matrices in near-linear time

We present new algorithms for computing the log-determinant of symmetric, diagonally dominant matrices. Existing algorithms run with cubic complexity with respect to the size of the matrix in the worst case. Our algorithm computes an approximation of the log-determinant in time near-linear with respect to the number of non-zero entries and with high probability. This algorithm builds upon the utra-sparsifiers introduced by Spielman and Teng for Laplacian matrices and ultimately uses their refined versions introduced by Koutis, Miller and Peng in the context of solving linear systems. We also present simpler algorithms that compute upper and lower bounds and that may be of more immediate practical interest.

• Publication year

  2014

• Venue

  arXiv.org

• Publication date

  2014-08-07

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1408.1693
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time

  2013cited by this paper
• Algorithms, Graph Theory, and Linear Equations in Laplacian Matrices

  2011cited by this paper
• Determinant Approximations

  2011cited by this paper
• A Nearly-m log n Time Solver for SDD Linear Systems

  2011influential reference
• Approaching Optimality for Solving SDD Linear Systems

  2010influential reference
• A Note on Preconditioning by Low-Stretch Spanning Trees

  2009cited by this paper
• Kriging and cross‐validation for massive spatial data

  2009cited by this paper
• Log-det approximation based on uniformly distributed seeds and its application to Gaussian process regression

  2008cited by this paper
• A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning

  2008cited by this paper
• Nearly Tight Low Stretch Spanning Trees

  2008cited by this paper
• Graph sparsification by effective resistances

  2008cited by this paper
• Approximate implementation of the logarithm of the matrix determinant in Gaussian process regression

  2007cited by this paper
• Log-determinant relaxation for approximate inference in discrete Markov random fields

  2006cited by this paper
• Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

  2006influential reference
• The Schur complement and its applications

  2005cited by this paper
• Analysis of Computer Experiments Using Penalized Likelihood in Gaussian Kriging Models

  2005cited by this paper
• Approximation of the Determinant of Large Sparse Symmetric Positive Definite Matrices

  2000influential reference
• Monte Carlo estimates of the log determinant of large sparse matrices

  1999influential reference
• Computer Solution of Large Linear Systems

  1999cited by this paper
• An Efficient Algorithm for QCD with Light Dynamical Quarks

  1998cited by this paper
• Sparse spatial autoregressions

  1997cited by this paper
• Some large-scale matrix computation problems

  1996cited by this paper
• Monte Carlo methods for estimating linear combinations of inverse matrix entries in lattice QCD

  1994cited by this paper
• Approximations to the determinant term in gaussian maximum likelihood estimation of some spatial models

  1992cited by this paper
• A Graph-Theoretic Game and its Application to the k-Server Problem (Extended Abstract)

  1991influential reference
• The role of elimination trees in sparse factorization

  1990cited by this paper
• Multigrid techniques for quark propagator

  1989cited by this paper
• Direct Methods for Sparse Matrices

  1987cited by this paper
• Molecular Quantum Mechanics

  1970cited by this paper
• Quantum Theory of Many-Particle Systems. III. Extension of the Hartree-Fock Scheme to Include Degenerate Systems and Correlation Effects

  1955cited by this paper

• On Randomized Trace Estimates for Indefinite Matrices with an Application to Determinants

  2020cites this paper
• Estimating the inverse trace using random forests on graphs

  2019cites this paper
• Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees

  2017cites this paper
• A Randomized Algorithm for Approximating the Log Determinant of a Symmetric Positive Definite Matrix

  2015cites this paper
• Large-Scale Log-Determinant Computation via Weighted L_2 Polynomial Approximation with Prior Distribution of Eigenvalues

  2015cites this paper