## 3 Supernodal Task-Based Approach  
### Positive-Definite Case (Hsl_ma87)  
We consider first the case when \(A\) is positive definite and briefly discuss the approach used by our supernodal sparse Cholesky solver HSL_MA87. This code is designed for use on multicore processors and is described in detail in [4]. Motivated by the work of [PERSON] _et al._[35, 36] on efficiently solving dense linear systems of equations on multicore processors, the factorization is divided into tasks, each of which alters a single block of the factor \(L\). The block size \(nb\) is a user-controlled parameter. The columns of each nodal matrix are split into blocks of \(nb\) columns (the last block column may have fewer than \(nb\) columns) and then each block column is split into blocks, each with \(nb\) rows (again, the last block may have fewer than \(nb\) rows). The tasks to be performed on each block are partially ordered and the dependencies between them implicitly represented by a directed acyclic graph (DAG), with a vertex for each task and an edge for each dependency. A task is ready for execution if and only if all tasks with incoming edges to it are completed. While the order of the tasks must obey the DAG, there remains much freedom for exploitation of parallelism. At the start of the computation, there is one task ready for each leaf of the assembly tree; the final task will be associated with the factorization of a root of the assembly tree. The DAG-based approach was adopted for HSL_MA87 since it offers significant improvements over utilizing more traditional fork-join parallelism by block columns. It avoids requiring all threads to finish their tasks for a block column before any thread can move on to the next block column. It also allows easy dynamic work sharing when another user or an asymmetric system load causes some threads to become slower than others. Such asymmetric loading can be common on multicore systems, caused either by operating system scheduling of other processes or by unbalanced triggering of hardware interrupts. The tasks within a sparse supernodal Cholesky factorization algorithm are as follows:  
**factorize_block(\(L_{diag}\))** This computes the traditional dense Cholesky factor \(L_{diag}\) of the triangular part of a block that is on the diagonal. If the block is trapezoidal, this is followed by a triangular solve of its rectangular part  
\[L_{rect}\Leftarrow L_{rect}L_{diag}^{-T}.\]
**solve_block(\(L_{dest}\))** This performs a triangular solve of an off-diagonal block by the Cholesky factor \(L_{diag}\) of the block on its diagonal, _i.e._,  
\[L_{dest}\Leftarrow L_{dest}L_{diag}^{-T}.\]  
**update_internal(\(L_{dest}\), \(scol\))** This performs the update of the block \(L_{dest}\) by the block column \(scol\) belonging to the same nodal matrix, _i.e._,  
\[L_{dest}\Leftarrow L_{dest}-L_{r}L_{c}^{T}\]  
where \(L_{r}\) is a block within \(scol\) and \(L_{c}\) is a submatrix in the same block column. **update_between(\(L_{dest}\), \(snode\), \(scol\))** This performs the update of the block \(L_{dest}\) by the block column \(scol\) of a descendant supernode _snode_ _i.e._,  
\[L_{dest}\Leftarrow L_{dest}-L_{r}L_{c}^{T}\]  
where \(L_{r}\) and \(L_{c}\) are submatrices of contiguous rows of \(scol\) that correspond to the rows and columns of \(L_{dest}\), respectively. The dense Cholesky factorization within the **factorize_block** task may be performed using subroutine _potrf from the LAPACK library [37] (a software library for numerical linear algebra that is built using the BLAS routines to effectively exploit the caches on cache-based architectures). The other tasks may be performed using BLAS-3 subroutines. There are some restrictions on the order in which the tasks are performed; for example, the updating of a block of a nodal matrix from a block column of \(L\) that is associated with one of the supernode's descendants has to wait for all the rows of the block column that it needs to become available.