Graph Coloring for Computing Derivatives
NSF and DOE Funded Project

Home | People | Papers | Presentations | Software | Automatic Differentiation

Papers

Sequential Algorithms

  • A.H. Gebremedhin, A. Pothen, A. Tarafdar and A. Walther,
    Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation,
    INFORMS Journal on Computing Vol 21, No 2, pp 209--223, 2009.
    Abstract.     Paper in PDF
  • A. H. Gebremedhin, A. Pothen and A. Walther,
    Exploiting Sparsity in Jacobian Computation via Coloring and Automatic Dierentiation:
    A Case Study in a Simulated Moving Bed process    ,
    In C. Bischof et al. (Eds.): Lecture Notes in Computational Science and Engineering 64, pp. 339-349, 2008, Springer.
    Proceeding of AD2008, The 5th International l Conference on AD, Bonn, Germany.
    Abstract.     Paper in PDF
  • A.H. 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 1042--1072, 2007.
    Abstract.     Paper in PDF
  • A.H. Gebremedhin, F. Manne and A. Pothen,
    What Color Is Your Jacobian? Graph Coloring for Computing Derivatives,
    SIAM Review, Vol 47, No 4, pp 629--705, 2005.
    Abstract     Paper in PDF

Parallel Algorithms

  • D. Bozdag, U. Catalyurek, A. H. Gebremedhin, F. Manne, E. Boman and F. Ozgunner,
    Efficient Distributed-memory Parallel Algorithms for Distance-2 Coloring
    and Their Application to Derivative Computation    ,
    SIAM J. Sci. Comput., Under Review, 2009.
    Abstract
  • D. Bozdag, A.H. Gebremedhin, F. Manne, E. 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 515--535, 2008.
    Abstract     Paper in PDF .

  • D. Bozdag, U.Catalyurek, A.H. Gebremedhin, F. Manne, E. G. Boman and F. Ozguner,
    A Parallel Distance-2 Graph Coloring Algorithm for Distributed Memory Computers,
    Lecture Notes in Computer Science,  vol 3726, 2005, pp 796 - 806, Springer.
    Proc. of HPCC 2005, Sept 21 - 25, 2005, Sorrento, Italy.
    Abstract.     Paper in PDF.
  • E.G. Boman, D.Bozdag, U.Catalyurek, A.H. Gebremedhin and F. Manne,
    A Scalable Parallel Graph Coloring Algorithm for Distributed Memory Computers,
    Lecture Notes in Computer Science, vol 3648 , 2005, pp 241 - 251, Springer.
    Proc. of EuroPar 2005, 30 Aug - 2 Sept, 2005, Lisboa, Portugal.
    Abstract.    Paper in PDF.
  • A.H. Gebremedhin, F. Manne and T. Woods,
    Speedingup Parallel Graph Coloring,
    Lecture Notes in Computer Science, vol 3732, 2005, Springer.
    Proc. of Para 2004,June 20--23, 2004, Lyngby, Denmark.
    Abstract.    Paper in PDF.
  • A.H. Gebremedhin, F. Manne and A. Pothen,
    Parallel Distance-k Coloring Algorithms for Numerical Optimization ,
    Lecture Notes in Computer Science, vol 2400, 2002, pp 912--921, Springer.
    Proc. of EuroPar 2002, Aug 27--30, 2002, Paderborn, Germany.
    Abstract.     Paper in PDF.

CSCAPES overview papers (with some coloring content)

  • E. Boman, D. Bozdag, U. Catalyurek, K. Devine, A. Gebremedhin, P. Hovland and A. Pothen,
    Combinatorial Algorithms for Computational Science and Engineering ,
    Journal of Physics: Conference Series 125 (2008) 012071, 5 pages; SciDAC 2008.
    Paper in PDF.   

  • E. Boman, D. Bozdag, U. Catalyurek, K. Devine, A. Gebremedhin, P. Hovland, A. Pothen and M.M. Strout,
    Enabling High Performance Computational Science throught Combinatorial Algorithms,
    Journal of Physics: Conference Series 78 (2007) 012058 (10 pp); SciDAC 2007.
    Paper in PDF.   

  • S. Bhomwick, 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), pp 453--457; SciDAC 2006.
    Paper in PDF