@Article{Kim:2014:PSD,
  author =       "Kyungjoo Kim and Victor Eijkhout",
  title =        "A Parallel Sparse Direct Solver via Hierarchical {DAG} Scheduling",
  journal =      "{ACM} Transactions on Mathematical Software",
  volume  =      41,
  number  =      1,
  accepted =     "28 January 2014",
  upcoming =     "true", 
  abstract =     "
                  We present a parallel sparse direct solver for multi-core
                  architectures based on Directed Acyclic Graph (DAG)
                  scheduling.  Recently, DAG scheduling has become
                  popular in advanced Dense Linear Algebra libraries
                  due to its efficient asynchronous parallel execution
                  of tasks. However, its application to sparse matrix
                  problems is more challenging as it has to deal with an
                  enormous number of highly irregular tasks. This typically
                  results in substantial scheduling overhead both in time
                  and space, which causes overall parallel performance to
                  be suboptimal. We describe a parallel solver based on
                  two-level task parallelism: tasks are first generated from
                  a parallel tree traversal on the assembly tree; next, those
                  tasks are further refined by using \textit{algorithms-by-blocks} to
                  gain fine-grained parallelism. The resulting fine-grained
                  tasks are asynchronously executed after their dependencies
                  are analyzed. Our approach is distinct from others in that
                  we adopt two-level task scheduling to mirror the two-level
                  parallelism. As a result we reduce scheduling overhead, and
                  increase efficiency and flexibility. The proposed parallel
                  sparse direct solver is evaluated for the particular
                  problems arising from the hp-Finite Element Method where
                  conventional sparse direct solvers do not scale well.",
}