Features
Clustering
PHI supports various clustering algorithms, which are listed in the following table:
- Binary Space Partitioning
- Based on coordinates for each index, cardinality or geometrically balanced binary space partitioning is implemented.
- Algebraic Clustering
- Using only the sparsity pattern and the coefficients of the sparse matrix an algebraic approach to clustering is implemented.
- Nested Dissection
- For BSP and for algebraic clustering, nested dissection is implemented as an optional clustering strategy, resulting in a very memory and time efficient structure.
H-Matrix Algebra
The following table gives an overview of the implemented H-matrix algebra in PHI.
- Matrix Construction
- Sequential and parallel construction of H-matrices and domain-decomposition matrices. In parallel case, online and offline scheduling is supported.
- Matrix-Vector Multiplication
- Multiplication of scalar, distributed and domain-decomposition based vectors with matrices
- Matrix Addition
- Sequential and parallel addition of arbitrary matrices. Online and offline scheduling is supported for parallel environments.
- Matrix Multiplication
- Sequential and parallel multiplication of H-matrices. Online and offline scheduling is supported for shared memory systems.
- Matrix Inversion
- Sequential and parallel matrix inversion based on Gaussian elimination. Parallel inversion with online scheduling supported for shared memory systems. Parallel inversion of domain decomposition matrices supported for shared and distributed memory machines.
- Matrix Decomposition (LU, Cholesky)
- Sequential and parallel decomposition of matrices. Offline scheduling based on data distribution supported for parallel environments.
Classical Solvers
Along with H-matrix based direct solvers, e.g. via inversion, several classical solvers are implemented in PHI, e.g. Richardson-iteration, CG, BiCG-Stab and GMRES. All solvers automatically exploit parallel matrix-vector multiplication and vector operations, implemented for the matrices and vectors.
Load-Balancing
PHI implements several load-balancing algorithms, e.g. list-, LPT-, multifit-scheduling and sequence-partitioning (along with space-filling curves). These can be used for offline scheduling of the workload. Furthermore, some algorithms support online-scheduling based on list-scheduling in the case of a shared-memory system.
Parallel Computation
PHI works in two different algorithm modes: threaded or by message passing. In the first case, all processors share the same address space and hence this is restricted to a shared memory machine. Managing threads is accomplished by the POSIX Threads interface, which is available on most operating systems.
For message passing based communication, either MPI or an internal pipe-based implementation is used. The latter is only available in a shared memory environment.
Dynamic Memory Management
PHI contains a special memory allocator which is optimised for H-matrices and multi-threaded environments. The results with this allocator are much better than with a standard allocator.
Rmalloc is also available as a library which can be used for other projects, since it is not restricted to H-matrices and showed very good performance with other types of programms.