CoinAbcBaseFactorization
Core ABC SIMD-optimized LU factorization implementation
Algorithm
ABC (Alternative Basis Code) LU Factorization: Enhanced sparse LU with modern CPU optimizations:
- Markowitz pivot selection with singleton detection
- SIMD-vectorized scatter/gather for column updates
- Cache-blocking (BLOCKING8) for L2/L3 efficiency
- Parallel elimination using Cilk (when ABC_PARALLEL=2)
- Hyper-sparse mode for very sparse intermediate results
B = L·U with row/column permutations P, Q: P·B·Q = L·U, where L unit lower triangular, U upper triangular Markowitz criterion: select pivot minimizing (r_i - 1)(c_j - 1)
Note: 32 bits assumed sufficient for row/column counts, but CoinBigIndex can be 64-bit for element indices.
Complexity: Factorization: $O(nnz × fill-in)$, highly structure-dependent FTRAN/BTRAN: $O(nnz(L)$ + nnz(U)) with SIMD acceleration SIMD speedup: 2-4x for dense column operations
See Also
- CoinAbcFactorization.hpp for instantiation
- CoinAbcHelperFunctions.hpp for SIMD kernels
Source
Header file: `src/CoinAbcBaseFactorization.hpp`