Pivoting Strategies
Pivoting strategies determine how rows and columns are selected during ACA compression. The choice of pivoting strategy significantly affects both the accuracy and computational cost of the approximation.
Value-Based Strategies
Value-based strategies select pivots by examining matrix entries to find the most significant components.
Maximum Value Pivoting
The maximum value strategy, also referred to as partial pivoting [1, 2], selects the pivot with the largest absolute value in the current residual. In the standard ACA when starting with the first row, all following columns are selected as:
\[\arg\max_{j} |\mathbf{v}_{r,j}|\]
and all rows for r > 1 are selected as:
\[\arg\max_{i} |\mathbf{u}_{r-1,i}|\]
API: MaximumValue
Random Sampling
Random sampling pivoting is typically combined with the random sampling convergence criterion or a combined convergence criterion. It selects the next row or column leveraging the randomly sampled entries of the underlying matrix used in the convergence criterion, choosing row or column of the sample with the maximum absolute error after iteration r:
\[\arg\max_{k} |\mathbf{e}_{r,k}|\]
where e_r contains the error of the sampled entries after the r-th iteration.
In the random sampling convergence criterion, the mean error of the random samples is used to estimate the overall residual error.
API: AdaptiveCrossApproximation.RandomSamplingPivoting
Geometry-Based Strategies
Geometry-based strategies exploit spatial information about the underlying point sets or basis functions.
Fill Distance
The fill distance strategy, following [3], selects the row or column associated with geometrical positions x ∈ X that minimize the fill distance:
\[h \coloneqq \sup_{x \in X} \mathrm{dist}(x, X_r)\]
where dist(x, X_r) = min_{y ∈ X_r} |x - y| and X_r is the set of already selected points associated with rows or columns after r iterations, from one step to the next. This strategy aims to cover the domain uniformly, ensuring that no region is left unrepresented.
Note: this strategy should be used only either for the rows or the columns, not both simultaneously and be combined with partial pivoting.
API: FillDistance
Modified Leja Points
Modified Leja points, following [5], follow a similar idea to the fill distance strategy but instead of minimizing the fill distance in each iteration select the node furthest away from the already selected points X_r:
\[\arg\max_i h_i\]
This approach results in a similar geometrical distribution as the fill distance strategy, however, it is significantly more efficient.
Note: this strategy should be used only either for the rows or the columns, not both simultaneously and be combined with partial pivoting.
API: Leja2
Mimicry Pivoting
Mimicry pivoting, following [7], approximates the pivot distribution of a fully pivoted ACA without requiring full matrix access. The pivot selection combines three principles:
- Angular distribution (uniform coverage)
- Boundary emphasis (Leja-like selection)
- Distance weighting (favor near-field contributions)
Formally, the pivot index is selected as:
\[j_r = \arg\max_{z \in \mathcal{Z}} \left[ \left(\min_{z_k \in \mathcal{Z}_f} \|z - z_k\|\right) \cdot \left(\prod_{z_k \in \mathcal{Z}_f} \|z - z_k\|\right)^{2/|\mathcal{Z}_f|} \cdot \left(\frac{1}{\|z - c\|}\right)^4 \right]\]
where:
\mathcal{Z}are candidate points,\mathcal{Z}_fare previously selected pivots,cis the cluster center.
This strategy
Note: this strategy should be used only either for the rows or the columns, not both simultaneously and be combined with partial pivoting.
API: MimicryPivoting
Tree Mimicry Pivoting
Tree mimicry pivoting extends the mimicry pivoting strategy by leveraging a hierarchical clustering of the geometric positions associated with the rows and columns. The hierarchical clustering of the positions hast to be passed to the pivoting strategy. For details see [7].
API: TreeMimicryPivoting
Combined Strategies
The combined pivoting strategy allows mixing different pivoting strategies combined with multiple convergence criteria, that decide which strategy to use at each step, enabling hybrid approaches.
API: AdaptiveCrossApproximation.CombinedPivStrat
Choosing a Strategy
The choice of pivoting strategy should be guided by the specific characteristics of the problem at hand, including the nature of the matrix, desired accuracy, and computational resources. In general the solid results are obtained using the maximum value pivoting strategy.
For spatial problems where the zeros blocks arise in the matrix structure, geometry-based strategies or random sampling pivoting can provide better performance. For details see [6].