Publications
Overview Papers and News Articles

B.A. Hendrickson and A. Pothen,
Combinatorial Scientific Computing: Past Successes, Current Opportunities, Future Challenges,
Chapter 1, in Combinatorial Scientific Computing, U. Naumann and O. Schenk (eds.), CRC/Chapman and Hall,
2011.

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;
Combinatorial Algorithms
for Petascale Science,
SciDAC Review, Issue 5, pp 2635,
Fall 2007.

E.G. Boman, D. Bozdag, U. Catalyurek, K. Devine, A.H. Gebremedhin, P. Hovland and A. Pothen,
Combinatorial Algorithms for Computational Science and Engineering,
Journal of Physics: Conference Series 125 (2008) 012071, 5 pp. SciDAC 2008.

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

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

B. Hendrickson, and A. Pothen,
Combinatorial
Scientific Computing: The enabling power of discrete algorithms in computational science,
Lecture Notes in Computer Science, Vol. 4395, pp. 260280, 2007.

M. Wolf and E. Boman,
Parallel Processing '08: An Increasing Role for Combinatorial Methods in
LargeScale Parallel Simulations,
SIAM News Vol 41, No 5, June 2008.

A.H. Gebremedhin,
The Third SIAM Workshop on Combinatorial Scientific Computing,
SIAM News Vol 40, No 4, May 2007.
Research Papers
Journal Papers:

U. Catalyurek, J. Feo, A.H. Gebremedhin, M. Halappanavar and A. Pothen,
Multithreaded Graph Coloring Algorithms,
Submitted Feb 2011.

I. Safro and B. Temkin,
Multiscale approach for the network compressionfriendly ordering,
Journal of Discrete Algorithms, 9:190202,
June 2011.

D. Ron, I. Safro, and A. Brandt,
Relaxationbased coarsening and multiscale graph organization,
Multiscale Modeling and Simulation, 9(1):407423, 2011.

M. Halappanavar, J. Feo, O. Villa, A. Tumeo, F. Dobrian, and A. Pothen,
Approximate weighted matching on emerging manycore and multithreaded architectures,
submitted for publication,
2011.

J. Chen and I. Safro,
Algebraic distance on graphs, under revision in SIAM Journal of Scientific Computing,
2010.

A.H. Gebremedhin, D. Nguyen, M.M.A. Patwary, and A. Pothen,
ColPack: Graph Coloring Software for Sparse Derivative Matrix Computation and Beyond,, Submitted Oct 2010.

D. Bozdag, U. Catalyurek, A.H. Gebremedhin, F. Manne, E.G. Boman, and F. Ozguner,
Distributedmemory Parallel Algorithms for Distance2 Coloring and Their Application to Derivative Computation,
SIAM Journal on Scientific Computing, Volume 32, Issue 4, pp 24182446, 2010.

B. Ucar, U. Catalyurek, and C. Aykanat,
A matrix partitioning interface to PaToH in MATLAB ,
Parallel Computing, to appear.

U. Catalyurek, C. Aykanat and E. Kayaaslan,
Hypergraph Partitioning Based FillReducing Ordering ,
Technical Report, OSUBMITR2009n02, The Ohio State University, Department of Biomedical Informatics, also available as BUCE0904, Bilkent University, Computer Engineering Department, 2009. Submitted for Publication.

U. Catalyurek, C. Aykanat, and B. Ucar,
On twodimensional sparse matrix partitioning: Models, Methods, and a Recipe,
SIAM Journal of Scientific Computing, Vol. 32, No. 2, pp. 656683, 2010.

E.G. Boman, and M.M. Wolf,
A Nested Dissection Approach to Sparse Matrix Partitioning for Parallel Computations,
Sandia Report 20085482J, 2008, Submitted for Publication.

U.V. Catalyurek, E.G. Boman, K.D. Devine, D. Bozdag, R.T. Heaphy, and L.A. Riesen,
A Hypergraph Repartitioning Model for Dynamic Load Balancing,
Journal of Parallel and Distributed Computing, Vol 69, Iss. 8, pp 711724, 2009.

D. W. Cranston, and P. D. Hovland,
Colorings for Efficient Derivative Computation on Grids with Periodic Boundaries,
Preprint ANL/MCSP15571108, 2008, Submitted for Publication.

L. Grigori, E.G. Boman, S. Donfack, and T.A. Davis,
Hypergraphbased
Unsymmetric Nested Dissection Ordering for Sparse LU Factorization,
Sandia Report 20081290J, 2008, Submitted for Publication.

D. Ron, I. Safro and A. Brandt,
A Fast Multigrid Algorithm for Energy Minimization under Planar Density Constraints,
Preprint ANL/MCSP15601108, 2008, Submitted for Publication.

A.H. Gebremedhin, A. Pothen, A. Tarafdar, and A. Walther,
Efficient Computation of Sparse Hessians using Coloring and Automatic Differentiation,
INFORMS Journal on Computing, 21(2):209223, 2009.

D. Bozdag, F. Ozguner, U. Catalyurek,
Compaction of Schedules and a TwoStage Approach for
DuplicationBased DAG Scheduling,
IEEE Transaction on Parallel and Distributed Systems,
Vol. 20, No. 6, pp 857871, June 2009.

I. Safro, D. Ron, and A. Brandt,
Multilevel algorithms for linear ordering problems,
Journal of Experimental Algorithmics, 13:1.41.20,
2008.

D. Bozdag, A.H. Gebremedhin, F. Manne, E.G. Boman, and U. Catalyurek,
A Framework for Scalable Greedy Coloring on Distributed Memory Parallel Computers,
Journal of Parallel and Distributed Computing,
Vol 68, No 4, pp 515535, 2008.

A. Lumsdaine, D. Gregor, B. Hendrickson and J. Berry,
Challenges in Parallel Graph Processing,
Parallel Processing Letters,
, 17(1):520, 2007.

P. Hovland, B. Norris, M. M. Strout, and J. Utke.,
Term Graphs for Computing Derivatives in Imperative Languages,
Electronic Notes in Theoretical Computer Science, Volume 176, Issue 1, 28 May 2007, Pages 99111.

A. Gebremedhin, A. Tarafdar, F. Manne and A. Pothen,
New Acyclic and Star Coloring Algorithms with Applications to Hessian Computation,
SIAM Journal on Scientific Computing, Vol 29, No 3, pp 10421072, 2007.

A. Gebremedhin, M. Essaidi, I. GuerinLassous, J. Gustedt, J.A. Telle,
PRO: A Model for the Design and Analysis of Efficient and Scalable Parallel Algorithms,
Nordic Journal of Computing, Vol 13, pp 125, 2006.
Conference Papers:

E. G. Boman and S. Rajamanickam,
A study of combinatorial issues in a sparse hybrid solver,
in Proceedings of SciDAC 2011, 2011.

M.M.A. Patwary, A.H. Gebremedhin and A. Pothen,
New Multithreaded Ordering and Coloring Algorithms for
Multicore Architectures.
In E. Jeannot, R. Namyst and J. Roman, editors, EuroPar 2011, volume 6853 of Lecture Notes in Computer Science, pages 250262. Springer, 2011.

S.H.K Narayanan, B. Norris, P. Hovland, D.C. Nguyen and A.H. Gebremedhin,
Sparse Jacobian Computation using ADIC2 and ColPack,
Procedia Computer Science, 4:21152123, 2011. Proceedings of the International Conference on Computational Science, ICCS 2011.

U. Catalyurek, F. Dobrian, A.H. Gebremedhin, M. Halappanavar,
and A. Pothen, Distributedmemory Parallel Algorithms for Matching and
Coloring, Proc. of IPDPS 2011, Workshop on Parallel Computing and
Optimization (PCO'11).

G. Teodoro, T. Hartley, U. Catalyurek, and R. Ferreira,
Runtime optimizations for replicated dataflows on heterogeneous environments ,
The ACM International Symposium on High Performance Distributed Computing (HPDC), 2010, to appear.

Michael M. Wolf, Michael A. Heroux, and Erik G. Boman,
Factors Impacting Performance of Multithreaded Sparse Triangular Solve ,
accepted at VECPAR'10.

E. Saule, D. Bozdag, and U. Catalyurek,
A Moldable Online Scheduling Algorithm and Its Application to Parallel Short Sequence Mapping ,
Proceedings of the 15th International Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP 2010),
in conjunction with IPDPS 2010, to appear.

D. Bozdag, A. Hatem and U. Catalyurek,
Exploring Parallelism in Short Sequence Mapping Using BurrowsWheeler Transform ,
Proceedings of 24th International Parallel and Distributed Processing Symposium (IPDPS),
9th IEEE International Workshop on High Performance Computational Biology, 2010, to appear.

B. Ucar and U. Catalyurek,
On scalability of hypergraph models for sparse matrix partitioning,
Proceedings of the PDP 2010: 18th Euromicro International Conference on Parallel, Distributed and NetworkBased Computing, Jan 2010.

S. H. K. Narayanan, B. Norris and B. Winnicka,
ADIC2 : development of a component source transformation system for differentiating C and C++ ,
in Proceedings of International Conference on Computational Science (ICCS 2010), pages 18451853, Elsevier
, 2010.

M. Strout, N. Osheim, D. Rostron, P. Hovland and A. Pothen,
Evaluation of Hierarchical Mesh Reorderings,
Proceedings of the International Conference on Computational Science (ICCS), May 2009.

E.G. Boman, U.V. Catalyurek, C. Chevalier,
K.D. Devine, I. Safro, and M.M. Wolf,
Advances in Parallel Partitioning, Load Balancing, and Matrix Ordering,
SciDAC09 Conference, San Diego, June 2009.

O. Roderick, and I. Safro,
Polynomial interpolation for predicting decisions and recovering missing data,
Preprint ANL/MCSP15860209, 2009, Submitted for Publication.

A. Lyons,
Restricted
Coloring Problems and Forbidden Induced Subgraphs,
Preprint ANL/MCSP16110409, 2009, Submitted for Publication.

D. Bozdag , C. Barbacioru and U. Catalyurek ,
Parallel Short Sequence Mapping for High Throughput Genome Sequencing,
23rd International Parallel and Distributed Processing Symposium (IPDPS'09).

I. Safro, P. Hovland, J. Shin, and M. Strout,
Improving random walk performance,
accepted in International Conference on Scientific Computing , 2009.

K. Devine, E. Boman, L.A. Riesen,
U. Catalyurek, C. Chevalier,
Getting Started With Zoltan: a Short Tutorial,
to appear in proceedings of Dagstuhl Seminar On Combinatorial Scientific Computing, Feb 2009.

C. Chevalier, and I. Safro,
Comparison of Coarsening Schemes for Multilevel Graph Partitioning,
to appear at the 3rd Workshop on Learning and Intelligent Optimization (LION3),
Trento, Italy, January 2009.

A. Lyons,
Acyclic and Star Colorings of Joins of Graphs and an Algorithm for Cographs,
in Proceedings of the Eighth Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW09), pages 199204,
2009.

M.M. Wolf, E.G. Boman, and B. Hendrickson,
Optimizing Parallel Sparse MatrixVector Multiplication by Corner Partitioning,
PARA08, Trondheim, Norway, May 2008, to appear in LNCS.

A.H. Gebremedhin, A. Pothen, and A. Walther,
Exploiting Sparsity in Jacobian Computation via Coloring and Automatic Differentiation:
a Case Study in a Simulated Moving Bed process,
In C. Bischof et al. (Eds.): Proceeding of AD2008, The 5th Int'l Conference on AD,
Lecture Notes in Computational Science and Engineering 64, pp. 339349,
2008, Springer.

H.S. AbdelKhalik, P. Hovland, A. Lyons, T. Stover and J. Utke,
A Low Rank Approach to Automatic Differentiation,
In C. Bischof et al. (Eds.): Proceeding of AD2008, The 5th Int'l Conference on AD,
Lecture Notes in Computational Science and Engineering 64, pp. 5565,
2008, Springer.

S. Bhowmick and P. Hovland,
A PolynomialTime Algorithm for Detecting Directed Axial Symmetry
in Hessian Computational Graphs,
In C. Bischof et al. (Eds.): Proceeding of AD2008, The 5th Int'l Conference on AD,
Lecture Notes in Computational Science and Engineering 64, pp. 91102,
2008, Springer.

A. Lyons and J. Utke, On the Practical Exploitation of Scarsity,
In C. Bischof et al. (Eds.): Proceeding of AD2008, The 5th Int'l Conference on AD,
Lecture Notes in Computational Science and Engineering 64, pp. 103114,
2008, Springer.

J. Shin, P. Malusare, and P. Hovland,
Design and Implementation of a ContextSensitive, FlowSensitive
Activity Analysis Algorithm for Automatic Differentiation,
In C. Bischof et al. (Eds.): Proceeding of AD2008, The 5th Int'l Conference on AD,
Lecture Notes in Computational Science and Engineering 64, pp. 115126,
2008, Springer.

I. Charpentier, C.D. Cappello, and J. Utke
Efficient HigherOrder Derivatives of
the Hypergeometric Function,
In C. Bischof et al. (Eds.): Proceeding of AD2008, The 5th Int'l Conference on AD,
Lecture Notes in Computational Science and Engineering 64, pp. 127137,
2008, Springer.

U.V. Catalyurek, E.G. Boman, K.D. Devine, D. Bozdag, R. Heaphy, L.A. Riesen,
Hypergraphbased Dynamic Load Balancing for Adaptive Scientific Computations,
Proceedings of 21st IEEE International Parallel and Distributed Processing Symposium (IPDPS07),
2007.
Won best paper award in the Algorithms track.
Book Chapters:

E.G. Boman, U.V. Catalyurek, C. Chevalier, K.D. Devine,
Parallel partitioning, coloring, and ordering for Scientific Computing with Zoltan,
Combinatorial Scientific Computing, editors Uwe Naumann and Olaf Schenk, submitted.

U.V. Catalyurek, D. Bozdag, E.G. Boman, K.D. Devine, R. Heaphy and L.A. Riesen,
Hypergraphbased Dynamic Partitioning and Load Balancing,
Advanced Computational Infrastructures for Parallel/Distributed Adaptive Applications, Wiley Press, M. Parashar, X. Li, S. Chandra, 2009, to appear.
PhD Theses

M. Wolf, Hypergraphbased combinatorial optimization of matrixvector multiplication,
PhD Thesis, University of Illinois at UrbanaChampaign, April 2009. Advisor: M. Heath.

M. Halappanavar, Algorithms for vertexweighted matching in graphs,
PhD Thesis, Old Dominion University, May 2009. Advisor: A. Pothen.

D. Bozdag, Graph Coloring and Clustering Algorithms for Science and Engineering Applications,
PhD Thesis, The Ohio State University, Dec 2008. Advisors: U. Catalyurek and F. Ozguner.
