Sandia National Laboratories
1416 Scalable Algorithms
Computing Research

Erik Boman


Many copyrights are held by the publisher. Preprints are provided for personal use only.
Can't find a paper? Try Google Scholar , Microsoft Academic Search, or the searchable index of all Sandia CS publications.

Hot papers (submitted but not yet published)

Popular Science

Journal Papers

Conference Papers

Book chapters


Hot manuscripts, not yet published (top of page)

A Distributed-Memory Hierarchical Solver for Sparse Matrices, C. Chen, H. Pouransari, S. Rajamanickam, E.G. Boman, E. Darve

Popular Science (top of page)

Combinatorial Algorithms for Petascale Science, A. Pothen, A.H. Gebremedhin, F. Dobrian; E.G. Boman, K.D. Devine, B.A. Hendrickson P. Hovland, B. Norris, J. Utke; U. Catalyurek; M.M. Strout; SciDAC Review, Issue 5, pp. 26--35, Fall 2007.

Journal Papers (top of page)

The Zoltan and Isorropia Parallel Toolkits for Combinatorial Scientific Computing: Partitioning, Ordering, and Coloring, E.G. Boman, U.V. Catalyurek, C. Chevalier, and K.D. Devine, Scientific Programming vol. 20, no. 2, pp. 129--150, 2012, special issue on Trilinos. (Preprint)

A Quasi-Algebraic Multigrid Approach to Fracture Problems Based on Extended Finite Elements, B. Hiriyur, R.S. Tuminaro, H. Waisman, E.G. Boman, and D.E. Keyes, SIAM J. Sci. Comp., vol. 34, pp. A603-A626 (Preprint)

Hypergraph-based Unsymmetric Nested Dissection Ordering for Sparse LU Factorization, L. Grigori, E.G. Boman, S. Donfack, and T.A. Davis, SIAM J. Sci. Comp., vol. 32, iss. 6, pp. 3426-3446, 2010. (An older version is Sandia Report 2008-1290J, 2008.).

Distributed-memory Parallel Algorithms for Distance-2 Coloring and Their Application to Derivative Computation, D. Bozdag, U. Catalyurek, A. Gebremedhin, F. Manne, E.G. Boman, F. Ozguner, SIAM J. Sci. Comp., Volume 32, Issue 4, pp. 2418-2446, 2010. (Tech. report 2009 available here .)

A Repartitioning Hypergraph Model for Dynamic Load Balancing, U.V. Catalyurek, E.G. Boman, K.D. Devine, D. Bozdag, R.T. Heaphy, and Lee Ann Riesen, JPDC vol. 69, iss. 8, pp. 711-724, 2009. (Preprint version: Sandia Report 2008-2304J )

The US Environmental Protection Agency uses Operations Research to Reduce Drinking Water Contamination Risks (Franz Edelman Award Finalist), R. Murray, W.E. Hart, C.A. Phillips, J. Berry, E.G. Boman, R. Carr, L.A. Riesen, J.P. Watson, et al., INFORMS Interfaces, vol 39, no. 1, Jan-Feb 2009, pp. 57-68. DOI: 10.1287/inte.1080.0415.

A Framework for Scalable Parallel Greedy Coloring on Distributed Memory Computers, D. Bozdag, A.H. Gebremedhin, F. Manne, E.G. Boman and U.V. Catalyurek, J. on Parallel and Distributed Computing, Vol 68, No 4, pp 515--535, 2008. (Preprint)

Optimal Embeddings and Eigenvalues in Support Theory, Erik G Boman, Stephen Guattery, Bruce Hendrickson, SIAM J. on Matrix Analysis, vol 29, no 2, pp. 596-605, 2007.

New Challenges in Dynamic Load-Balancing, K. Devine et al, Applied Numerical Mathematics, v 52, pp. 133-152, 2005.

Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners, E.G. Boman, B. Hendrickson, and S. Vavasis, SIAM J. on Numerical Analysis, v.46, no. 6, pp. 3264-3284, 2008. ArXiv version.

On Factor Width and Symmetric H-matrices, E.G. Boman, D. Chen, O. Parekh, S. Toledo, Lin. Alg. Appl., vol 405, pp. 239-248, Aug 2005 ( preprint version)

Support Theory for Preconditioning, E. G. Boman and B. Hendrickson, SIAM J. of Matrix Analysis, vol. 25, no. 3, pp. 694-717, 2004. (Get a copy for your personal use )

Maximum-Weight-Basis Preconditioners, E. G. Boman, D. Chen, B. Hendrickson, and S. Toledo, Numerical Linear Algebra with Applications, vol 11 issue 8-9 pp. 695-721, 2004.

Zoltan: Data Management Services for Parallel Dynamic Applications, Karen Devine, Erik Boman, Robert Heaphy, Bruce Hendrickson and Courtenay Vaughan, Computing in Science and Engineering, vol 4, no 2, pp. 90-97, 2002.

A Spectral Algorithm for Seriation and the Consecutive Ones Problem, J. E. Atkins, E. G. Boman, and B. Hendrickson, SIAM J. of Computing, vol. 28, no. 1, pp. 297-310, 1998. (Get a copy for your personal use)

Conference Papers (top of page)

Parallel Graph Coloring for Manycore Architectures, M. Deveci, E.G. Boman, K.D. Devine, and S. Rajamanickam, IPDPS'16, 2016. preprint

An Empirical Comparison of Graph Laplacian Solvers, Erik G. Boman, K. Deweese, John R. Gilbert, ALENEX16, Jan. 2016.

Domain Decomposition Preconditioners for Communication-Avoiding Krylov Methods on a Hybrid CPU/GPU Cluster, I. Yamazaki, S. Rajamanickam, E. G. Boman, M. A. Heroux, M. Hoemmen, and S. Tomov, Proc. of SC14, Nov. 2014.

Scalable Matrix Computations on Scale-Free Graphs Using 2D Graph Partitioning, E.G. Boman, K.D. Devine, S. Rajamanickam, Proc. of SC13, Nov. 2013.

A Nested Dissection Method for Parallel Sparse Matrix-Vector Multiplication, E.G. Boman and Michael M. Wolf, HPEC 2013.

An Evaluation of the Zoltan Parallel Graph and Hypergraph Partitioners, S. Rajamanickam, E.G. Boman, the 10th DIMACS Implementation Challenge, Atlanta, Feb. 2012.

ShyLU: A Hybrid-Hybrid Solver for Multicore Platforms, S. Rajamanickam, E.G. Boman, M.A. Heroux, IPDPS'12, pp. 631-643. (Preprint)

Multithreaded Algorithms for Maximum Matching in Bipartite Graphs, A. Azad, M. Halappanavar, S. Rajamanickam, E.G. Boman, A. Khan, A. Pothen, IPDPS'12, pp. 860-872. ( Preprint )

Enabling Next-Generation Parallel Circuit Simulation with Trilinos, C. Baker, E. Boman, M. Heroux, E. Keiter, S. Rajamanickam, R. Schiek, and H. Thornquist, Workshop on High-Performance Scientific Software (HPSS2011) at Euro-Par 2011, Aug. 2011, Bordeaux, France. LNCS Volume 7155, pp. 315-323, 2012.

A Study of Combinatorial Issues in a Sparse Hybrid Solver, E.G. Boman and S. Rajamanickam, SciDAC'11.

Factors Impacting Performance of Multithreaded Sparse Triangular Solve, Michael M. Wolf, Michael A. Heroux, and Erik G. Boman, Proceed. of VECPAR'10, to be published in LNCS, also SANDIA Technical Report SAND2010-0331.

An Accurate Hypergraph Model for Mesh Partitioning, Cedric Chevalier and Erik G. Boman, SIAM Workshop on Combinatorial Scientific Computing, Seaside, Oct. 2009. Also available as Sandia Report SAND-2009-3896A. (Related poster available upon request.)

A Parallel Preconditioning Strategy for Efficient Transistor-Level Circuit Simulation, H. K. Thornquist, E. R. Keiter, R. J. Hoekstra, D. M. Day, E. G. Boman, Proceedings of the International Conference on Computer-Aided Design 2009 (ICCAD 2009), pp. 410-417, 2009.

Advances in Parallel Partitioning, Load Balancing, and Matrix Ordering, E.G. Boman, U.V. Catalyurek, C. Chevalier, K.D. Devine, I. Safro, M.M. Wolf, J. of Physics: Conference Series, vol. 180, 012008. (SciDAC09 Conference, San Diego, June 2009.) doi: 10.1088/1742-6596/180/1/012008

Getting Started With Zoltan: A Short Tutorial, K.D. Devine, E.G. Boman, L.A. Riesen, U.V. Catalyurek, C. Chevalier, Proc. of Dagstuhl Symposium on Combinatorial Scientific Computing, 2009

Combinatorial Algorithms for Computational Science and Engineering, E.G. Boman, D. Bozdag, U.V. Catalyurek, K.D. Devine, A.H. Gebremedhin, P.D. Hovland, and A. Pothen, SciDAC 2008, J. of Physics: Conference Series 125, 012071 (6 pages), 2008. DOI: 10.1088/1742-6596/125/1/012071

Optimizing Parallel Sparse Matrix-Vector Multiplication by Corner Partitioning, M. M. Wolf, E.G. Boman and B. Hendrickson, PARA08, Trondheim, Norway, May 2008.

Low-memory Lagrangian relaxation methods for sensor placement in municipal water networks, C.A. Phillips, J. Berry, E.G. Boman, L.A. Riesen, Proc. of World Environmental and Water Resources Congress 2008, ASCE 2008.

The TEVA-SPOT Toolkit for Drinking Water Contaminant Warning System Design, W.E. Hart, C.A. Phillips, J. Berry, E.G. Boman, R. Murray, L.A. Riesen, J.P. Watson, Proc. of World Environmental and Water Resources Congress 2008, ASCE, 2008.

Limited Memory Techniques for Sensor Placement in Water Distribution Networks, W.E Hart, J. Berry, E.G. Boman, C.A. Phillips, L.A. Riesen, J.P. Watson, Workshop on Learning and Intelligent Optimization (LION-2), Nov 2007.

A Nested Dissection Approach to Sparse Matrix Partitioning, Erik G. Boman, ICIAM'07, Proc. Appl. Math. and Mech., Volume 7 Issue 1, pp. 1010803 - 1010804. (DOI: 10.1002/pamm.200700703)

Enabling high performance computational science through combinatorial algorithms, E.G. Boman, D. Bozdag, U.V. Catalyurek, K.D. Devine, A.H. Gebremedhin, P. Hovland, A. Pothen and M.M. Strout, Journal of Physics: Conference Series 78, 012058 (2007), SciDAC 2007.

Hypergraph-based Dynamic Load Balancing for Adaptive Scientific Computations, U.V. Catalyurek, E.G. Boman, K.D. Devine, D. Bozdag, R.T. Heaphy, and Lee Ann Riesen, IPDPS'07. Winner of "Best Paper" award in the Algorithms track!

Combinatorial Algorithms Enabling Computational Science: Tales from the Front, S. Bhowmick, E. Boman, K. Devine, A. Gebremedhin, B. Hendrickson, P. Hovland, T. Munson and A. Pothen, Journal of Physics: Conference Series 46 (2006), 453--457, SciDAC 2006.

Parallel Hypergraph Partitioning for Scientific Computing, K.D. Devine, E.G. Boman, R.T. Heaphy, R. Bisseling, and U.V. Catalyurek, IPDPS'06, April 2006.

A Parallel Distance-2 Graph Coloring Algorithm for Distributed Memory Computers, D. Bozdag, U. Catalyurek, A. Gebremedhin, F. Manne, E.G. Boman, F. Ozguner, HPCC 2005, Sept. 2005.

A Scalable Parallel Graph Coloring Algorithm for Distributed Memory Computers, E.G. Boman, D. Bozdag, U. Catalyurek, A. Gebremedhin, F. Manne, Euro-Par 2005, LNCS, v. 3648, pp. 241-251, 2005.

An Iterative Approach to Computing Directions of Negative Curvature, E.G. Boman and W. Murray, presented at the Copper Mountain Conference on Iterative Methods, March 1998.

A Multilevel Algorithm for Reducing the Envelope of Sparse Matrices, E. G. Boman and B. Hendrickson, Tech.Rep. SCCM-96-14, Stanford University, 1996; also presented at the SIAM Appl. Lin. Alg. conference in Oct 1997.

Book Chapters (top of page)

"Parallel Partitioning with Zoltan: Is Hypergraph Partitioning Worth It?", S. Rajamanickam and E. G. Boman, in Graph Partitioning and Graph Clustering, AMS Contemporary Mathematics, vol. 588, pp. 37-52 (10th DIMACS Implementation Challenge special issue). (Preprint.)

Parallel Partitioning, Ordering, and Coloring in Scientific Computing, E.G. Boman, U.V. Catalyurek, C. Chevalier, K.D. Devine, in Combinatorial Scientific Computing, U. Naumann and O. Schenk (eds), CRC Press, 2012.

Hypergraph-based Dynamic Partitioning and Load-Balancing, U.V. Catalyurek, D. Bozdag, K.D. Devine, E.G. Boman, R.T. Heaphy, L.A. Riesen, in "Advanced Computational Infrastructures for Parallel and Distributed Adaptive Applications", Manish Parashar et al. (eds), Wiley 2008.

Partitioning and Load Balancing for Emerging Parallel Applications, Karen D. Devine, Erik G. Boman, George Karypis, in "Parallel Processing for Scientific Computing", edited by M.A. Heroux, P. Raghavan, and H.D. Simon, SIAM 2006.

Other (top of page)

A Comparison of Preconditioners for Solving Linear Systems Arising from Graph Laplacians, Kevin Deweese and Erik G. Boman, SAND-2013-9772P, to appear in the CSRI Summer 2013 Proceedings, Sandia National Laboratories, 2013.

Infeasibility and Negative Curvature in Optimization, Ph.D. thesis, Stanford University, Feb. 1999.

Top of page

(505) 844-2003 (Phone)

Mailing address (USPS)
Sandia National Laboratories
P.O. Box 5800, MS 1318
Albuquerque, NM 87185-1319

Sandia National Laboratories
1515 Eubank SE
MS 1318
Albuquerque, NM 87123