  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.
