publications

 


Journal articles and selected Conference papers


In the pipeline:


Accelerating Sparse Cholesky Factorization on GPUs, Steve Rennich, Darko Stosic, and T. A. Davis, Parallel Computing, posted online (http://dx.doi.org/10.1016/j.parco.2016.06.004), to appear.


Sparse QR factorization on the GPU, S. N. Yeralan, T. A. Davis, S. Ranka, and W. Sid-Lakhdar, submitted to ACM Trans. on Mathematical Software. (see qrgpu_paper.pdf for tech report).


In print:


An Efficient Hybrid Algorithm for the Separable Convex Quadratic Knapsack Problem, T. A. Davis, W. W. Hager, and J. T. Hungerford, ACM Trans. on Mathematical Software, Volume 42 Issue 3, June 2016 . (click here for PDF). http://dx.doi.org/10.1145/2828635


A Survey of Direct Methods for Sparse Linear Systems, T. Davis, S. Rajamanickam, and W. Sid-Lakhdar, Acta Numerica, 2016, vol 25, pp 383-566. (click here for PDF of tech report),  http://dx.doi.org/10.1017/S0962492916000076.  See survey.bib for a complete bibtex file for all references in the paper, and a list of the references themselves is in references.pdf.


Toward using direct methods in seismic tomography: computation of the full resolution matrix using high performance computing and sparse QR factorization, P. Bogiatzis, M. Ishii, and T. A. Davis, Geophysical Journal International 205 (2), 830-836, 2016 (for tech report, click here and here).  http://dx.doi.org/10.1093/gji/ggw052


State-defect constraint pairing graph coarsening method for Karush–Kuhn–Tucker matrices arising in orthogonal collocation methods for optimal control, Begum Senses, Anil Rao, T. Davis.  Computational Optimization and Applications, 2016.

http://dx.doi.org/10.1007/s10589-015-9821-x


Graph Theory (II.16), with Y. Hu, and Searching a Graph (VI.10), Princeton Companion to Applied Mathematics, Ed. N. Higham et al., Princeton Univ. Press, 2015.


Graph Coarsening Method for KKT Matrices Arising from Orthogonal Collocation Methods for Optimal Control Problems, Begum Senses, T. A. Davis, Anil V. Rao, 56th AIAA/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference, Jan 2015, Kissimmee, FL (click here for PDF).


Accelerating Sparse Cholesky Factorization on GPUs, Steve Rennich, Darko Stosic, and T. A. Davis, IA3 Workshop on Irregular Applications: Architectures and Algorithms (held in conjunction with SC14), Nov 16, 2014, New Orleans.  (click here for PDF).


Algorithm 933: Reliable Calculation of Numerical Rank, Null Space Bases, Pseudoinverse Solutions and Basic Solutions using SuiteSparseQR Leslie V. Foster and T. A. Davis, ACM Transactions on Mathematical Software, Vol 40, Issue 1, pp. 7:1 - 7:23, 2013.  (click here for PDF)


Algorithm 930: FACTORIZE: an object-oriented linear system solver for MATLAB T. A. Davis, ACM Transactions on Mathematical Software, Vol 39, Issue 4, pp. 28:1 - 28:18, 2013. (click here for PDF)


An exact reanalysis algorithm using incremental Cholesky factorization and its application to crack growth modeling, Matthew J. Pais, Sencer N. Yeralan, Timothy A. Davis, Nam H. Kim, International Journal for Numerical Methods in Engineering

Volume 91, Issue 12, 2012, pp 1358 - 1364. (click here for PDF)


The University of Florida sparse matrix collection, Timothy A. Davis, Yifan Hu, ACM Transactions on Mathematical Software, Vol 38, Issue 1, 2011, pp 1:1 - 1:25.  (click here for PDF)


Algorithm 915, SuiteSparseQR: Multifrontal multithreaded rank-revealing sparse QR factorization, Timothy A. Davis, ACM Transactions on Mathematical Software, Vol 38, Issue 1, 2011, pp 8:1 - 8:22.  (click here for PDF)


Hypergraph-based unsymmetric nested dissection ordering for sparse LU factorization, L. Grigori, E. Boman, S. Donfack, and T. A. Davis, SIAM Journal on Scientific Computing, Vol 32, Issue 6, 2010, pp 3426 - 3446. (click here for PDF)


Algorithm 907: KLU, A Direct Sparse Solver for Circuit Simulation Problems, Timothy A. Davis, Ekanathan Palamadai Natarajan, ACM Transactions on Mathematical Software, Vol 37, Issue 6, 2010, pp 36:1 - 36:17.  (click here for PDF)


Dynamic Supernodes in Sparse Cholesky Update/Downdate and Triangular Solves, Timothy A. Davis, William W. Hager ACM Transactions on Mathematical Software, Vol 35, Issue 4, 2009, pp 27:1 - 27:23.  (click here for PDF)


Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate, Yanqing Chen, Timothy A. Davis, William W. Hager, Sivasankaran Rajamanickam, ACM Transactions on Mathematical Software, Vol 35, Issue 3, 2008, pp 22:1 - 22:14.  (click here for PDF)


A sparse proximal implementation of the LP Dual Active Set Algorithm, T. A. Davis and W. W. Hager, Mathematical Programming, Vol 112, Issue 2, 2008, pp. 275 - 301. (click here for PDF)


Dual multilevel optimization, T. A. Davis and W. W. Hager, Mathematical Programming, Vol 112, Issue 2, April 2008, pp. 403 - 425. (click here for PDF)


Algorithm 849: A concise sparse Cholesky factorization package, Timothy A. Davis, ACM Transactions on Mathematical Software, Vol 31, Issue 4, 2005, pp 587 - 591.  (click here for PDF)


Model representation with aesthetic computing: Method and empirical study, Paul Fishwick, Timothy Davis, Jane Douglas, ACM Transactions on Modeling and Computer Simulation, Vol 15, Issue 3, 2005, pp 254 - 279.  (click here for PDF)


Row modifications of a sparse Cholesky factorization, T. A. Davis and W. W. Hager, SIAM Journal on Matrix Analysis and Applications, Vol 26, Issue 3, 2005, pp. 621 - 639. (click here for PDF)


Algorithm 837: AMD, an approximate minimum degree ordering algorithm, Patrick R. Amestoy, Timothy A. Davis, Iain S. Duff, ACM Transactions on Mathematical Software, Vol 30, Issue 3, 2004, pp 381 - 388.  (click here for PDF)


Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm, Timothy A. Davis, John R. Gilbert, Stefan I. Larimore, Esmond G. Ng

ACM Transactions on Mathematical Software, Vol 30, Issue 3, 2004, pp 377 - 380.  (click here for PDF)


A column approximate minimum degree ordering algorithm, Timothy A. Davis, John R. Gilbert, Stefan I. Larimore, Esmond G. Ng, ACM Transactions on Mathematical Software, Vol 30, Issue 3, 2004, pp 353 - 376.  (click here for PDF)


Algorithm 832: UMFPACK V4.3---an unsymmetric-pattern multifrontal method, Timothy A. Davis, ACM Transactions on Mathematical Software (TOMS), Vol 30, Issue 2, pp 196 - 199, 2004.  (click here for PDF)


A column pre-ordering strategy for the unsymmetric-pattern multifrontal method, Timothy A. Davis, ACM Transactions on Mathematical Software (TOMS), Vol 30, Issue 2, pp 165 - 195, 2004.  (click here for PDF)


Multiple-rank modifications of a sparse Cholesky factorization, T. A. Davis and W. W. Hager, SIAM Journal on Matrix Analysis and Applications, Vol 22, Issue 4, pp. 997 - 1013, 2001. (click here for PDF)


Modifying a sparse Cholesky factorization, T. A. Davis and W. W. Hager, SIAM Journal on Matrix Analysis and Applications, Vol 20, Issue 3, pp. 606 - 627, 1999. (click here for PDF)


A combined unifrontal/multifrontal method for unsymmetric sparse matrices,

Timothy A. Davis, Iain S. Duff, ACM Transactions on Mathematical Software (TOMS), Vol 25, Issue 1, pp 1 - 20, 1999.  (click here for PDF)


An unsymmetric-pattern multifrontal method for sparse LU factorization, T. A. Davis and I. S. Duff, SIAM Journal on Matrix Analysis and Applications, Vol 18, Issue 1, pp. 140 - 158, 1997. (click here for PDF)


An approximate minimum degree ordering algorithm, P. Amestoy, T. A. Davis, and I. S. Duff, SIAM Journal on Matrix Analysis and Applications, Vol 17, Issue 4, pp. 886 - 905, Dec. 1996. (click here for PDF)


A concurrent dynamic task graph, T. Johnson, T. A. Davis, and S. M. Hadfield, Parallel Computing, Vol 22, Issue 2, pp. 327 - 333, Feb. 1996.  (click here for PDF)


Multifrontal vs. frontal techniques for chemical process simulation on supercomputers, S. E. Zitney, J. Mallya, T. A. Davis, and M. A. Stadtherr, J. Computers and Chemical Engineering, Vol 20, Issue 6/7, pp. 641 - 646, 1996. (click here for PDF)


The use of graph theory in a parallel multifrontal method for sequences of unsymmetric pattern sparse matrices, S. M. Hadfield and T. A. Davis, Congressus Numerantium, Vol 108, pp. 43 - 52, 1995.


Parallel buddy memory management, T. Johnson and T. A. Davis, Parallel Processing Letters, Vol 2, Issue 4, pp. 391 - 398, 1992.


A nondeterministic parallel algorithm for general unsymmetric sparse LU factorization, T. A. Davis and P.-C. Yew, SIAM Journal on Matrix Analysis and Applications, Vol 11, Issue 3, pp. 383 - 402, 1990.


Pairwise reduction for the direct, parallel solution of sparse unsymmetric sets of linear equations, T. A. Davis and E. S. Davidson, IEEE Transactions on Computers, Vol 37, Issue 12, pp. 1648 - 1654, 1988.




Books

Direct Methods for Sparse Linear Systems, Timothy A. Davis, SIAM, Philadelphia, Sept. 2006. (DOI). Click here for a series of 42 lectures on the topic.  The software for the book is here: CSparse.zip.

MATLAB Primer, 8th edition, Timothy A. Davis, CRC Press, 2010.  Click here for files referenced in the book.