TDTimothy A. Davis

Timothy A. Davis

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Timothy A. Davis has a total of 87 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Algorithm 1xxx: ParU: a parallel task-based sparse multifrontal unsymmetric LU factorization

    by Mohsen Aznaveh, Timothy A. Davis, Wissam M. Sid-Lakhdar

    ParU is a sparse direct solver based on a novel parallel multifrontal algorithm. In contrast with UMFPACK, which draws its performance from highly customized data structures and parallel BLAS libraries, the goal of ParU is to maximize the sources of parallelism it can exploit through OpenMP tasking and nested parallelism, i.e., node -level parallelism within its rectangular frontal matrices, and tree -level parallelism across the assembly tree. ParU relies on the analysis phase of UMFPACK, with the addition of strategies to exploit tree parallelism. The factorization phase is based on a variant of the multifrontal method, where the fronts are unsymmetric and rectangular shaped. Similarly to UMFPACK, it exploits sparse pivots within the fronts, but simplifies the data structures to allow for coarser-grained node parallelism (mostly through large GEMM (matrix multiplication) and TRSM (triangular solve)). Experimental results show that ParU is competitive in terms of performance with state-of-the-art libraries as UMFPACK, SuperLU, and MUMPS.

  • Open Access

    Binsparse: A Specification for Cross-Platform Storage of Sparse Matrices and Tensors

    by Benjamin Brock, Willow Ahrens, Hameer Abbasi, Timothy A. Davis, Juni Kim, James Kitchen, Spencer Patty, Isaac Virshup, Erik Welch

    Sparse matrices and tensors are ubiquitous throughout multiple subfields of computing. The widespread usage of sparse data has inspired many in-memory and on-disk storage formats, but the only widely adopted storage specifications are the Matrix Market and FROSTT file formats, which both use ASCII text. Due to the inefficiency of text storage, these files typically have larger file sizes and longer parsing times than binary storage formats, which directly store an in-memory representation to disk. This can be a major bottleneck; since sparse computation is often bandwidth-bound, the cost of loading or storing a matrix to disk often exceeds the cost of performing a sparse computation. While it is common practice for practitioners to develop their own, custom, non-portable binary formats for high-performance sparse matrix storage, there is currently no cross-platform binary sparse matrix storage format. We present Binsparse, a cross-platform binary sparse matrix and tensor format specification. Binsparse is a modular, embeddable format, consisting of a JSON descriptor, which describes the matrix or tensor dimensions, type, and format, and a series of binary arrays, which can be stored in all modern binary containers, such as HDF5, Zarr, or NPZ. We provide several reference implementations of Binsparse spanning 5 languages, 5 frameworks, and 4 binary containers. We evaluate our Binsparse format on every matrix in the SuiteSparse Matrix Collection and a selection of tensors from the FROSTT collection. The Binsparse HDF5 CSR format shows file size reductions of 2.4x on average without compression and 7.5x with compression. We evaluate our parser's read/write performance against a state-of-the-art Matrix Market parser, demonstrating warm cache mean read speedups of 26.5x without compression and 2.6x with compression, and write speedups of 31x without compression and 1.4x with compression.


  • Open Access

    Algorithm 1050: SPEX Cholesky, LDL, and Backslash for Exactly Solving Sparse Linear Systems

    by Lorena Mejia-Domenzain, Jinhao Chen, Christopher Lourenco, Erick Moreno-Centeno, Timothy A. Davis

    SPEX Cholesky, SPEX LDL, and SPEX Backslash are software packages for exactly solving sparse linear systems, \(A\mathbf{x}=\mathbf{b}\) . SPEX Cholesky, used for symmetric positive definite (SPD) systems, computes an integral Cholesky factorization to solve the system \(A\mathbf{x}=\mathbf{b}\) in time proportional to arithmetic work—to date the only algorithm for SPD linear systems with this property. SPEX LDL extends SPEX Cholesky for symmetric negative definite and symmetric indefinite matrices with exclusively non-zero leading principal minors. SPEX Backslash is a general-purpose exact solver that automatically determines the best ordering and factorization to exactly solve the system \(A\mathbf{x}=\mathbf{b}\) . Computationally, we test the accuracy of MATLAB sparse backslash, the state-of-the-art collection of sparse matrix solvers, revealing it is near perfect for 87% of the tested instances. In addition, we show that SPEX Cholesky outperforms alternate exact solvers in runtime; specifically, SPEX Cholesky outperforms the exact solver Linbox and exact LU factorization on 70% and 92% of tested instances, respectively. Each of SPEX Cholesky, SPEX LDL, and SPEX Backslash is implemented in C and is accompanied by easy-to-use Python and MATLAB interfaces. They are distributed via GitHub, as a component of the SPEX software package, and as component of SuiteSparse.


  • A Genomic Tree-Based Sparse Solver

    by Timothy A. Davis, Srinivas Subramanian

  • Open Access

    Algorithm 1037: SuiteSparse:GraphBLAS: Parallel Graph Algorithms in the Language of Sparse Linear Algebra

    by Timothy A. Davis

    SuiteSparse:GraphBLAS is a full parallel implementation of the GraphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and types. When applied to sparse adjacency matrices, these algebraic operations are equivalent to computations on graphs. A description of the parallel implementation of SuiteSparse:GraphBLAS is given, including its novel parallel algorithms for sparse matrix multiply, addition, element-wise multiply, submatrix extraction and assignment, and the GraphBLAS mask/accumulator operation. Its performance is illustrated by solving the graph problems in the GAP Benchmark and by comparing it with other sparse matrix libraries.


  • Open Access

    Hypersparse Network Flow Analysis of Packets with GraphBLAS

    by Tyler Trigg, Chad Meiners, Sandeep Pisharody, Hayden Jananthan, Michael Jones, Adam Michaleas, Timothy Davis, Erik Welch, William Arcand, David Bestor, et al.

    Internet analysis is a major challenge due to the volume and rate of network traffic. In lieu of analyzing traffic as raw packets, network analysts often rely on compressed network flows (netflows) that contain the start time, stop time, source, destination, and number of packets in each direction. However, many traffic analyses benefit from temporal aggregation of multiple simultaneous netflows, which can be computationally challenging. To alleviate this concern, a novel netflow compression and resampling method has been developed leveraging GraphBLAS hyperspace traffic matrices that preserve anonymization while enabling subrange analysis. Standard multitemporal spatial analyses are then performed on each subrange to generate detailed statistical aggregates of the source packets, source fan-out, unique links, destination fan-in, and destination packets of each subrange which can then be used for background modeling and anomaly detection. A simple file format based on GraphBLAS sparse matrices is developed for storing these statistical aggregates. This method is scale tested on the MIT SuperCloud using a 50 trillion packet netflow corpus from several hundred sites collected over several months. The resulting compression achieved is significant (<0.1 bit per packet) enabling extremely large netflow analyses to be stored and transported. The single node parallel performance is analyzed in terms of both processors and threads showing that a single node can perform hundreds of simultaneous analyses at over a million packets/sec (roughly equivalent to a 10 Gigabit link).

  • Open Access

    Algorithm 1021: SPEX Left LU, Exactly Solving Sparse Linear Systems via a Sparse Left-looking Integer-preserving LU Factorization

    by Christopher Lourenco, Jinhao Chen, Erick Moreno-Centeno, Timothy A. Davis

    SPEX Left LU is a software package for exactly solving unsymmetric sparse linear systems. As a component of the sparse exact (SPEX) software package, SPEX Left LU can be applied to any input matrix, A , whose entries are integral, rational, or decimal, and provides a solution to the system \( Ax = b \) , which is either exact or accurate to user-specified precision. SPEX Left LU preorders the matrix A with a user-specified fill-reducing ordering and computes a left-looking LU factorization with the special property that each operation used to compute the L and U matrices is integral. Notable additional applications of this package include benchmarking the stability and accuracy of state-of-the-art linear solvers and determining whether singular-to-double-precision matrices are indeed singular. Computationally, this article evaluates the impact of several novel pivoting schemes in exact arithmetic, benchmarks the exact iterative solvers within Linbox, and benchmarks the accuracy of MATLAB sparse backslash. Most importantly, it is shown that SPEX Left LU outperforms the exact iterative solvers in run time on easy instances and in stability as the iterative solver fails on a sizeable subset of the tested (both easy and hard) instances. The SPEX Left LU package is written in ANSI C, comes with a MATLAB interface, and is distributed via GitHub, as a component of the SPEX software package, and as a component of SuiteSparse.


  • Open Access

    Seismic doublets and a complex seismic sequence controlled by the rotation of the Juan Fernández microplate

    by Simone Cesca, Carla Valenzuela Malebrán, José Ángel López-Comino, Timothy Davis, Carlos Tassara, Onno Oncken, Torsten Dahm

    A complex seismic sequence took place in 2014 at the Juan Fernández microplate, a small microplate located between Pacific, Nazca and Antarctica plates. Despite the remoteness of the study region and the lack of local data, we were able to resolve earthquake source parameters and to reconstruct the complex seismic sequence, by using modern waveform-based seismological techniques. The sequence started with an exceptional Mw 7.1-6.7 thrust – strike slip earthquake doublet, the first subevent being the largest earthquake ever recorded in the region and one of the few rare thrust earthquakes in a region otherwise characterized by normal faulting and strike slip earthquakes. The joint analysis of seismicity and focal mechanisms suggest the activation of E-W and NE-SW faults or of an internal curved pseudofault, which is formed in response to the microplate rotation, with alternation of thrust and strike-slip earthquakes. Seismicity migrated Northward in its final phase, towards the microplate edge, where a second doublet with uneven focal mechanisms occurred. The sequence rupture kinematics is well explained by Coulomb stress changes imparted by the first subevent. Our analysis show that compressional stresses, which have been mapped at the northern boundary of the microplate, but never accompanied by large thrust earthquakes, can be accommodated by the rare occurrence of large, impulsive, shallow thrust earthquakes, with a considerable tsunamigenic potential.

  • Open Access

    Algorithm 1003

    by Timothy A. Davis, William W. Hager, Scott P. Kolodziej, S. Nuri Yeralan

    Partitioning graphs is a common and useful operation in many areas, from parallel computing to VLSI design to sparse matrix algorithms. In this article, we introduce Mongoose, a multilevel hybrid graph partitioning algorithm and library. Building on previous work in multilevel partitioning frameworks and combinatoric approaches, we introduce novel stall-reducing and stall-free coarsening strategies, as well as an efficient hybrid algorithm leveraging (1) traditional combinatoric methods and (2) continuous quadratic programming formulations. We demonstrate how this new hybrid algorithm outperforms either strategy in isolation, and we also compare Mongoose to METIS and demonstrate its effectiveness on large and social networking (power law) graphs.


  • Top Cited Papers
    Open Access

    Algorithm 1000

    by Timothy A. Davis

    SuiteSparse:GraphBLAS is a full implementation of the GraphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and types. When applied to sparse adjacency matrices, these algebraic operations are equivalent to computations on graphs. GraphBLAS provides a powerful and expressive framework for creating graph algorithms based on the elegant mathematics of sparse matrix operations on a semiring. An overview of the GraphBLAS specification is given, followed by a description of the key features and performance of its implementation in the SuiteSparse:GraphBLAS package.