Assefaw Gebremedhin's projects

Assefaw Gebremedhin, Software

Parallel Maximum Clique Finder (PMC)

This is implementation of fast algorithms for maximum clique finding and related problem in large graphs that are designed to exploit features of social and information networks. See here for info on the code and its usage.

Associated Paper: R.A. Rossi, D.F. Gleich, A.H. Gebremedhin and M.M.A. Patwary, Fast maximum clique algorithms for large graphs , Poster Proceedings of WWW2014, 2014.

LIVARH

Software for Live-variables based Hessian computation via Automatic Differentiation (implelemted on top of ADOL-C). Code and further information available here.

Associated Paper: M. Wang, A.H. Gebremedhin and A. Pothen, Capitalizing on Live Variables: New Algorithms for Efficient Hessian Computation via Automatic Differentiation. Submitted (journal), Nov 2014.

ColPack

ColPack is a software package consisting of implementations of fast and effective algorithms for a variety of graph coloring, vertex ordering, and related problems. Many of the coloring problems model partitioning needs arising in compression-based computation of Jacobian and Hessian matrices using Automatic Differentiation. Several of the coloring problems also find important applications in various areas outside derivative computation. ColPack is implemented in C++ in an object-oriented fashion heavily using STL.

Download: The source code of ColPack is freely distributed under the GNU Lesser General Public License. Download the latest version here.

Short API Documentation: Here is a short document describing the major interface functions of ColPack. Short doc.

Doxygen Documentation: And here is a complete doxygen documentation of ColPack (made by Duc Nguyen). Complete Doxygen documentation

Associated Paper: the following paper discusses the design, analysis, implementation, and performance evaluation of the underlying coloring algorithms in ColPack. If you use ColPack in your research, this paper is the best source to cite.
- Assefaw H. Gebremedhin, Duc Nguyen, Md. Mostofa Ali Patwary and Alex Pothen. ColPack: Software for Graph Coloring and Related Problems in Scientific Computing. ACM Transactions on Mathematical Software, Vol 40, No 1, pp 1-31, 2013. (also available at http://dl.acm.org/citation.cfm?doid=2513109.2513110)

ColPack, Other Tools, and Impact (selected stories)

In collaboration with Andrea Walther of Paderborn University, ColPack has been coupled with ADOL-C, a widely-used Algorithmic Differentiation (AD) software tool based on operator overloading. ADOL-C relies on ColPack for its sparse derivative computation capabilities and expects users to download ColPack when they use ADOL-C. The ADOLC-ColPack toolkit is used by a number of research groups in academia as well as in industry.

In our own research, we have used the toolkit to solve large-scale optimization problems in several applications. One example is a throughput optimization problem in a simulation of a purification process in chemical engineering (see this paper for details). Another example is a power flow optimization problem in electric grids (see this paper for details).

ColPack has also recently been interfaced with the source-to-source transformation AD tool ADIC2 of Argonne National Laboratory (see this paper for details). The toolkit has been used to efficiently compute gradients of partially separable functions (see this paper for details).