API Reference

ACA{RowPivType,ColPivType,ConvCritType}

Adaptive Cross Approximation (ACA) compressor for low-rank matrix approximation.

Computes M ≈ U * V by iteratively selecting rows and columns (pivots) until a convergence criterion is met. The algorithm starts with row, samples it to select a column pivot, then alternates between row and column selection.

Fields

• rowpivoting::RowPivType: Strategy for selecting row pivots
• columnpivoting::ColPivType: Strategy for selecting column pivots
• convergence::ConvCritType: Convergence criterion to stop iterations

(aca::ACA)(rowidcs::AbstractArray{Int}, colidcs::AbstractArray{Int})

Create a specialized ACA instance for a submatrix defined by index sets.

Initializes pivoting functors with the provided row and column indices. Used internally for hierarchical matrix compression.

Arguments

• rowidcs: Row indices of the submatrix
• colidcs: Column indices of the submatrix

Returns

New ACA instance with initialized pivoting state for the given indices.

ACA(; rowpivoting=MaximumValue(), columnpivoting=MaximumValue(),
      convergence=FNormEstimator(1e-4))

Construct an ACA compressor with keyword arguments.

Keyword Arguments

• rowpivoting: Row pivot selection strategy (default: MaximumValue())
• columnpivoting: Column pivot selection strategy (default: MaximumValue())
• convergence: Convergence criterion (default: FNormEstimator(1e-4))

(aca::ACA{P,P,C})(A, colbuffer, rowbuffer, maxrank; kwargs...)

Convenience method that initializes pivoting functors when using uniform strategies.

Delegates to the main computational routine after creating index-specialized functors. Only available when both pivoting strategies are of the same stateless type P <: PivStrat.

See the main (aca::ACA)(A, colbuffer, rowbuffer, rows, cols, rowidcs, colidcs, maxrank) method for detailed argument documentation.

(aca::ACA)(A, colbuffer, rowbuffer, rows, cols, rowidcs, colidcs, maxrank)

Compute ACA approximation with preallocated buffers (main computational routine).

Fills colbuffer and rowbuffer with low-rank factors U and V such that A[rowidcs, colidcs] ≈ U * V. Uses deflation to ensure orthogonality of pivots.

Arguments

• A: Matrix or matrix-like object (must support nextrc! interface)
• colbuffer::AbstractArray{K}: Buffer for U factors, size (length(rowidcs), maxrank)
• rowbuffer::AbstractArray{K}: Buffer for V factors, size (maxrank, length(colidcs))
• rows::Vector{Int}: Storage for selected row indices
• cols::Vector{Int}: Storage for selected column indices
• rowidcs::Vector{Int}: Global row indices of the block to compress
• colidcs::Vector{Int}: Global column indices of the block to compress
• maxrank::Int: Maximum number of pivots (hard limit on rank)

Returns

• npivot::Int: Number of pivots computed (≤ maxrank). The approximation is A[rowidcs, colidcs] ≈ colbuffer[:, 1:npivot] * rowbuffer[1:npivot, :]

ACAᵀ{RowPivType,ColPivType,ConvCritType}

Column-first variant of adaptive cross approximation. Starts by selecting columns first, then rows. Dual of standard ACA.

Fields

• rowpivoting::RowPivType: Strategy for selecting row pivots
• columnpivoting::ColPivType: Strategy for selecting column pivots
• convergence::ConvCritType: Convergence criterion

(aca::ACAᵀ)(rowidcs::AbstractArray{Int}, colidcs::AbstractArray{Int})

Initialize ACAᵀ functor with index sets. Creates functors for pivoting strategies bound to specific index ranges.

Arguments

• rowidcs::AbstractArray{Int}: Row indices for this compression
• colidcs::AbstractArray{Int}: Column indices for this compression

ACAᵀ(; rowpivoting=MaximumValue(), columnpivoting=MaximumValue(), convergence=FNormEstimator(1e-4))

Construct column-first ACA compressor with specified strategies.

Arguments

• rowpivoting: Row pivoting strategy (default: MaximumValue())
• columnpivoting: Column pivoting strategy (default: MaximumValue())
• convergence: Convergence criterion (default: FNormEstimator(1e-4))

(aca::ACAᵀ{P,P,C})(A, colbuffer, rowbuffer, maxrank; kwargs...)

Convenience method that initializes pivoting functors when using uniform strategies.

Delegates to the main computational routine after creating index-specialized functors. Only available when both pivoting strategies are of the same stateless type P <: PivStrat.

See the main (aca::ACAᵀ)(A, colbuffer, rowbuffer, rows, cols, rowidcs, colidcs, maxrank) method for detailed argument documentation.

(aca::ACAᵀ)(A, colbuffer, rowbuffer, maxrank; rows, cols, rowidcs, colidcs)

Perform column-first ACA compression. Computes low-rank approximation A ≈ colbuffer * rowbuffer by iteratively selecting columns then rows.

Arguments

• A: Matrix to compress
• colbuffer::AbstractArray{K}: Pre-allocated column storage (nrows × maxrank)
• rowbuffer::AbstractArray{K}: Pre-allocated row storage (maxrank × ncols)
• maxrank::Int: Maximum number of pivots
• rows: Selected row indices (optional, pre-allocated)
• cols: Selected column indices (optional, pre-allocated)
• rowidcs: Active row index range (optional)
• colidcs: Active column index range (optional)

Returns

• npivot::Int: Number of pivots computed

CombinedConvCrit

Composite convergence criterion combining multiple criteria. Converges when any constituent criterion is satisfied.

Fields

• crits::Vector{ConvCrit}: Vector of convergence criteria to combine
• isconverged::Vector{Bool}: Convergence status for each criterion

(convcrit::CombinedConvCrit)(K::AbstractMatrix, rowidcs, colidcs)

Initialize combined criterion functors. Handles special initialization for sampling-based criteria.

Arguments

• K::AbstractMatrix: Matrix to compress
• rowidcs::AbstractArray{Int}: Active row indices
• colidcs::AbstractArray{Int}: Active column indices

CombinedConvCritFunctor

Stateful convergence criterion combining multiple criteria. Converges when all criteria are satisfied.

Fields

• crits::Vector{ConvCritFunctor}: Vector of convergence criteria to combine
• isconverged::Vector{Bool}: Convergence status for each criterion

(convcrit::CombinedConvCritFunctor)(rowbuffer, colbuffer, npivot, maxrows, maxcolumns)

Check convergence using all combined criteria. Returns when any criterion signals convergence.

Arguments

• rowbuffer::AbstractMatrix{K}: Row factor buffer
• colbuffer::AbstractMatrix{K}: Column factor buffer
• npivot::Int: Current pivot index
• maxrows::Int: Number of active rows
• maxcolumns::Int: Number of active columns

Returns

• npivot::Int: Final pivot count
• continue::Bool: Whether to continue iteration (true if any criterion satisfied)

CombinedPivStrat

Composite pivoting strategy that switches between multiple strategies based on convergence.

Combines multiple pivoting strategies with a combined convergence criterion, allowing the pivot selection method to change as different convergence criteria are satisfied. For example, can start with geometric pivoting and switch to value-based pivoting once a certain accuracy is reached.

Fields

• strats::Vector{PivStrat}: Ordered list of pivoting strategies to use

(pivstrat::CombinedPivStrat)(convergence::CombinedConvCritFunctor, idcs::AbstractArray{Int})

Create a combined pivoting functor for the given index subset.

Initializes all constituent strategies with the provided indices and links them to the combined convergence criterion. Handles special cases like RandomSamplingPivoting which requires the convergence criterion functor rather than indices.

Arguments

• convergence::CombinedConvCritFunctor: Combined convergence criterion
• idcs::AbstractArray{Int}: Indices for the submatrix

Returns

• CombinedPivStratFunctor: Initialized combined strategy with functors for all sub-strategies

CombinedPivStratFunctor

Staeful functor of composite pivoting strategy that switches between multiple strategies based on convergence.

Combines multiple pivoting strategies with a combined convergence criterion, allowing the pivot selection method to change as different convergence criteria are satisfied. For example, can start with geometric pivoting and switch to value-based pivoting once a certain accuracy is reached.

Fields

• convcrit::CombinedConvCritFunctor: Combined convergence criterion tracking which sub-criteria are met
• strats::Vector{PivStratFunctor}: Ordered list of pivoting strategies to use

(pivstrat::CombinedPivStratFunctor)(rc::AbstractArray)

Select next pivot using the first strategy whose convergence criterion is met.

Iterates through the convergence criteria and uses the strategy corresponding to the first satisfied criterion. If no criteria are met, uses the first strategy. Automatically updates the convergence tracking state.

Arguments

• rc::AbstractArray: Row or column data for pivot selection

Returns

• Pivot index selected by the active strategy

(pivstrat::CombinedPivStratFunctor)()

Select initial pivot using the first strategy.

Delegates to the first strategy in the list for initial pivot selection when no data is available yet.

Returns

• Initial pivot index from the first strategy

ConvCrit

Abstract base type for convergence criteria. Convergence criteria determine when to stop the ACA iteration based on approximation quality.

ConvCritFunctor

Abstract base type for stateful convergence criterion functors. Used during compression to track convergence state across iterations.

ConvPivStrat <: PivStrat

Abstract type for convergence-driven pivoting strategies.

These strategies adapt their behavior based on convergence information or use randomization to improve robustness.

Concrete Types

• RandomSampling: Random pivot selection for convergence estimation

ConvPivStratFunctor <: PivStratFunctor

Abstract type for stateful convergence-driven pivoting functors.

FNormEstimator{F} <: ConvCrit

Frobenius norm-based convergence criterion for standard ACA.

Fields

• tol::F: Relative tolerance threshold

(cc::FNormEstimator{F})()

Initialize FNormEstimator functor with zero accumulated norm.

FNormEstimatorFunctor{F} <: ConvCritFunctor

Stateful Frobenius norm estimator for ACA compression. Tracks squared norm of UV factorization across iterations and stops iteration when relative error estimate falls below tolerance.

Fields

• normUV²::F: Accumulated squared Frobenius norm of UV
• tol::F: Relative tolerance threshold

(convcrit::FNormEstimatorFunctor)(rowbuffer, colbuffer, npivot, maxrows, maxcolumns)

Check convergence for standard ACA using Frobenius norm estimate. Returns (npivot, continue) where continue is true if iteration should proceed.

Arguments

• rowbuffer::AbstractMatrix{K}: Row factor buffer
• colbuffer::AbstractMatrix{K}: Column factor buffer
• npivot::Int: Current pivot index
• maxrows::Int: Number of active rows
• maxcolumns::Int: Number of active columns

Returns

• npivot::Int: Final pivot count
• continue::Bool: Whether to continue iteration

FNormExtrapolator{F} <: ConvCrit

Convergence criterion using polynomial extrapolation of pivot norms. Combines norm estimation with quadratic extrapolation to predict convergence.

Fields

• estimator::Union{FNormEstimator{F},iFNormEstimator{F}}: Underlying norm estimator

FNormExtrapolator(tol::F)

Construct extrapolator with Frobenius norm estimator.

Arguments

• tol::F: Convergence tolerance

(cc::FNormExtrapolator{F})()

Initialize extrapolator functor with empty history.

FNormExtrapolatorFunctor{F} <: ConvCritFunctor

Stateful extrapolator tracking pivot norm history. Fits quadratic polynomial to log-scaled norms for convergence prediction.

Fields

• lastnorms::Vector{F}: History of pivot norms for extrapolation
• estimator::Union{FNormEstimatorFunctor{F},iFNormEstimatorFunctor{F}}: Active estimator functor

(convcrit::FNormExtrapolatorFunctor)(rowbuffer, colbuffer, npivot, maxrows, maxcolumns)

Check convergence for ACA using extrapolation. Fits quadratic to log-norms and extrapolates to predict convergence.

Arguments

• rowbuffer::AbstractMatrix{K}: Row factor buffer
• colbuffer::AbstractMatrix{K}: Column factor buffer
• npivot::Int: Current pivot index
• maxrows::Int: Number of active rows
• maxcolumns::Int: Number of active columns

Returns

• npivot::Int: Final pivot count
• continue::Bool: Whether to continue iteration

(convcrit::FNormExtrapolatorFunctor)(rcbuffer::AbstractVector{K}, npivot::Int)

Check convergence for iACA using extrapolation. Applies extrapolation to incomplete ACA norm history.

Arguments

• rcbuffer::AbstractVector{K}: Current row or column buffer
• npivot::Int: Current pivot index

Returns

• npivot::Int: Final pivot count
• continue::Bool: Whether to continue iteration

FillDistance{D,F<:Real} <: GeoPivStrat

Geometric pivoting strategy based on fill distance minimization.

Selects pivots to minimize the fill distance, promoting well-distributed sampling in geometric space.

Fields

• pos::Vector{SVector{D,F}}: Geometric positions of all points (D-dimensional)

Type Parameters

• D: Spatial dimension
• F: Floating point type for coordinates

(pivstrat::FillDistance{D,F})(idcs::AbstractArray{Int})

Create a FillDistanceFunctor for the given index subset.

Initializes the functor with positions corresponding to idcs, preparing it for pivot selection within the submatrix.

Arguments

• idcs::AbstractArray{Int}: Indices of points to consider

Returns

• FillDistanceFunctor: Initialized functor with distance tracking

FillDistanceFunctor{D,F<:Real} <: PivStratFunctor

Stateful functor for fill distance pivot selection.

Maintains the minimum distances from each point to the set of selected points, updating them as new pivots are chosen.

Fields

• h::Vector{F}: Current minimum distance from each point to selected points
• pos::Vector{SVector{D,F}}: Geometric positions corresponding to indices

(pivstrat::FillDistanceFunctor{D,F})(::AbstractArray)

Select the next pivot minimizing the fill distance with respect to the selected points and updates the distance vector h for subsequent iterations.

Arguments

• ::AbstractArray: Row/column data (unused, selection is purely geometric)

Returns

• nextidx::Int: Index of the point maximizing fill distance

GeoPivStrat <: PivStrat

Abstract type for geometric/spatial pivoting strategies.

These strategies select pivots based on spatial/geometric properties rather than matrix values. Useful when geometric information about rows/columns is available.

Concrete Types

• FillDistance: Maximizes minimum distance to already selected points
• Leja2: Maximizes product of distances to selected points

GeoPivStratFunctor <: PivStratFunctor

Abstract type for stateful geometric pivoting functors.

Leja2{D,F<:Real} <: GeoPivStrat

Geometric pivoting strategy based on Leja points (product of distances).

A modified more efficient version of the fill distance approach. This leads to well-separated point sequences. These points have been introduced as modified leja points and will, therefore, be referred to as Leja2 points within this package.

Fields

• pos::Vector{SVector{D,F}}: Geometric positions of all points (D-dimensional)

Type Parameters

• D: Spatial dimension
• F: Floating point type for coordinates

(pivstrat::Leja2{D,F})(idcs::AbstractArray{Int})

Create a Leja2Functor for the given index subset.

Initializes the functor with positions corresponding to idcs, preparing it for pivot selection within the submatrix.

Arguments

• idcs::AbstractArray{Int}: Indices of points to consider

Returns

• Leja2Functor: Initialized functor with distance tracking

Leja2Functor{D,F<:Real} <: PivStratFunctor

Stateful functor for modified leja point pivot selection.

Maintains minimum distances from each point to all selected points, which are updated incrementally as new pivots are chosen.

Fields

• h::Vector{F}: Current minimum distance from each point to selected points
• idcs::Vector{Int}: Indices of points being considered for selection
• pos::Vector{SVector{D,F}}: Geometric positions corresponding to indices

(pivstrat::Leja2Functor{D,F})(::AbstractArray)

Select the next pivot with maximum minimum distance to selected points.

Chooses the point that is farthest from the set of already selected points, then updates the distance vector for subsequent iterations.

Arguments

• ::AbstractArray: Row/column data (unused, selection is purely geometric)

Returns

• nextidx::Int: Index of the point with maximum distance to selected points

MaximumValue <: ValuePivStrat

Pivoting strategy that selects the index with maximum absolute value.

This is the standard pivoting strategy used in classical ACA algorithms also referred to as partial pivoting. At each iteration, it chooses the row or column with the largest absolute value among the unused indices, ensuring numerical stability and good approximation quality.

(::MaximumValue)(idcs::AbstractArray{Int})

Create a MaximumValueFunctor for the given index array.

Returns a functor with tracking vector sized to match the length of idcs.

MaximumValueFunctor <: ValuePivStratFunctor

Stateful functor that tracks which indices have been used during pivot selection.

Created by calling a MaximumValue instance with length or index information. Maintains a boolean vector to ensure each index is selected at most once.

Fields

• usedidcs::Vector{Bool}: Tracks which indices have been selected as pivots

(pivstrat::MaximumValueFunctor)(rc::AbstractArray)

Select the unused index with maximum absolute value in rc.

Searches through all unused indices, finds the one with largest abs(rc[i]), marks it as used, and returns its index.

Arguments

• rc::AbstractArray: Row or column data to select from

Returns

• nextidx::Int: Index of the maximum absolute value among unused indices

(pivstrat::MaximumValueFunctor)()

Select the first index as the initial pivot.

Returns 1 and marks it as used. Used when no row/column data is available yet.

MimicryPivoting{D,F<:Real} <: GeoPivStrat

Geometric pivoting strategy that mimics point distribution of a fully pivoted ACA geometrically.

Selects pivots to reproduce the spatial distribution of a fully pivoted ACA. The strategy balances three objectives: geometric separation (Leja-like behavior), proximity to the reference distribution, and fill distance maximization. Particularly useful for H²–matrix compression where incomplete factorizations are sufficient.

Fields

• refpos::Vector{SVector{D,F}}: Positions of test or expansion domain
• pos::Vector{SVector{D,F}}: Positions from which to select pivots

Type Parameters

• D: Spatial dimension
• F: Floating point type for coordinates

(strat::MimicryPivoting{D,F})(refidcs, rcidcs)

Create a MimicryPivotingFunctor for the given reference and candidate indices.

Initializes the functor by computing the centroid of the reference points and setting up weights that favor points close to this centroid. This encourages the selected pivots to spatially mimic the reference distribution.

Arguments

• refidcs: Indices of reference points (e.g., parent cluster pivots)
• rcidcs: Indices of candidate points to select from (e.g., child cluster points)

Returns

• MimicryPivotingFunctor: Initialized functor with computed weights and metrics

MimicryPivotingFunctor{D,F<:Real} <: GeoPivStratFunctor

Functor for mimicry-based pivot selection.

Maintains vectors for leja2 (h), leja (leja), and weights (w) based on distance to reference centroid.

Fields

• pos::Vector{SVector{D,F}}: All geometric positions
• idcs::Vector{Int}: Current indices being considered for selection
• h::Vector{F}: Minimum distances from each point to selected points (fill distance)
• leja::Vector{F}: Product of distances to all selected points (Leja metric)
• w::Vector{F}: Weights based on inverse distance to reference centroid

(strat::MimicryPivotingFunctor{D,F})(npivot::Int)

Select next pivot balancing Leja separation, fill distance, and reference proximity.

Uses a composite metric that combines:

• Leja product (geometric separation from all selected points)
• Fill distance (maximum minimum distance criterion)
• Reference weights (proximity to target distribution)

The balance between these factors evolves with iteration number npivot.

Arguments

• npivot::Int: Current pivot iteration number (influences weight balance)

Returns

• Global index of the selected pivot point

(strat::MimicryPivotingFunctor{D,F})()

Select the first pivot based on proximity to reference centroid.

Chooses the point with maximum weight (closest to the reference centroid), then initializes distance metrics for subsequent pivot selection.

Returns

• Global index of the selected pivot point

PivStrat

Abstract base type for pivoting strategies in cross approximation algorithms.

Pivoting strategies determine which row or column to select at each iteration of the ACA algorithm. Concrete subtypes are typically stateless and callable, creating stateful PivStratFunctor instances when invoked with index information.

Subtypes by Category

• GeoPivStrat: Geometric strategies (e.g., fill distance, Leja points)
• ValuePivStrat: Value-based strategies (e.g., maximum absolute value)
• ConvPivStrat: Convergence-driven strategies (e.g., random sampling)

Interface

Concrete subtypes should implement:

• (strategy::MyPivStrat)(len::Int): Create functor for len indices
• (strategy::MyPivStrat)(idcs::AbstractArray{Int}): Create functor for index array

PivStratFunctor

Abstract base type for stateful pivoting functors.

Functors maintain state during the pivot selection process (e.g., tracking which indices have been used). Created by calling a PivStrat instance with index information.

Interface

Concrete subtypes should implement:

• (functor::MyPivStratFunctor)(): Select initial pivot (no data available)
• (functor::MyPivStratFunctor)(rc::AbstractArray): Select next pivot based on row/column data

RandomSampling{F<:Real} <: ConvCrit

Convergence criterion based on random matrix entry sampling. Monitors approximation error at randomly sampled positions.

Fields

• nsamples::Int: Number of random samples to take
• factor::F: Factor for automatic sample count (nsamples = factor * (nrows + ncols))
• tol::F: Convergence tolerance

(cc::RandomSampling)(K::AbstractMatrix{T}, rowidcs, colidcs)

Initialize random sampling functor with sampled matrix entries.

Arguments

• K::AbstractMatrix{T}: Matrix to compress
• rowidcs::AbstractArray{Int}: Active row indices
• colidcs::AbstractArray{Int}: Active column indices

RandomSampling(; factor=1.0, nsamples=0, tol=1e-4)

Construct random sampling convergence criterion.

Arguments

• factor::F: Multiplier for automatic sample count (default: 1.0)
• nsamples::Int: Fixed sample count (default: 0, use factor instead)
• tol::F: Convergence tolerance (default: 1e-4)

RandomSamplingFunctor{F<:Real,K} <: ConvCritFunctor

Stateful random sampling convergence checker. Tracks residual error at sampled matrix entries across iterations.

Fields

• normUV²::F: Squared Frobenius norm of approximation
• indices::Matrix{Int}: Sampled matrix positions (nsamples × 2)
• rest::Vector{K}: Residual values at sampled positions
• tol::F: Convergence tolerance

(convcrit::RandomSamplingFunctor)(rowbuffer, colbuffer, npivot, maxrows, maxcolumns)

Check convergence using random sampling. Updates residuals at sampled positions and compares to tolerance.

Arguments

• rowbuffer::AbstractMatrix{K}: Row factor buffer
• colbuffer::AbstractMatrix{K}: Column factor buffer
• npivot::Int: Current pivot index
• maxrows::Int: Number of active rows
• maxcolumns::Int: Number of active columns

Returns

• npivot::Int: Final pivot count
• continue::Bool: Whether to continue iteration

RandomSamplingPivoting <: ConvPivStrat

Pivoting strategy that uses the error of random sampling from the convergence estimation.

Instead of selecting pivots based on maximum values or geometric properties, this strategy chooses pivots from randomly sampled indices used by a random sampling convergence criterion. Works in conjunction with RandomSamplingFunctor to provide statistically based pivot selection.

Fields

• rc::Int: Index indicating which coordinate (row=1 or column=2) to select from

(pivstrat::RandomSamplingPivoting)(convcrit::RandomSamplingFunctor{F,K})

Create a RandomSamplingPivotingFunctor linked to the convergence criterion.

Initializes the functor by connecting it to the random sampling convergence criterion that tracks sampled indices and residuals.

Arguments

• convcrit::RandomSamplingFunctor{F,K}: Random sampling convergence functor

Returns

• RandomSamplingPivotingFunctor: Initialized functor linked to the criterion

RandomSamplingPivotingFunctor{F,K} <: ConvPivStratFunctor

Stateful functor for random sampling-based pivot selection.

Links to a random sampling convergence criterion functor to access the randomly sampled indices and their residuals, selecting pivots from the worst-performing samples.

Fields

• convcrit::RandomSamplingFunctor{F,K}: Convergence criterion with sample information
• rc::Int: Coordinate index (1 for row, 2 for column)

(pivstrat::RandomSamplingPivotingFunctor{F,K})(::AbstractArray)

Select pivot from the sample with largest residual.

Examines the random samples tracked by the convergence criterion and returns the row or column index (depending on rc) corresponding to the sample with the maximum residual error.

Arguments

• ::AbstractArray: Row/column data (unused, selection based on random samples)

Returns

• Index from the worst-performing random sample

TreeMimicryPivoting{D,T,TreeType} <: GeoPivStrat

Tree-aware mimicry pivoting strategy.

This strategy adapts the MimicryPivoting idea to a hierarchical tree of clusters. Instead of selecting individual points directly, it navigates the tree to pick clusters and then nodes within those clusters so that the selected pivots mimic a reference distribution at multiple scales.

Fields

• refpos::Vector{SVector{D,T}}: Reference positions to mimic (e.g., parent pivots)
• pos::Vector{SVector{D,T}}: Candidate point positions
• tree::TreeType: Tree structure providing cluster centers, children and values

Type parameters

• D: spatial dimension
• T: numeric type for coordinates
• TreeType: type of the tree adapter (must implement center, values, children, firstchild)

TreeMimicryPivoting(refpos, pos, tree)

Convenience constructor inferring tree type. refpos and pos must be vectors of SVector{D,T} coordinates and tree must provide required methods.

(pivstrat::TreeMimicryPivoting)(F, refidcs, maxrank)

Initialize a tree-aware mimicry functor.

F is a vector of tree node candidates (e.g., root children). The function computes the reference centroid from refidcs and allocates usedidcs of length maxrank for storing selected point indices.

TreeMimicryPivotingFunctor{D,T,TreeType} <: GeoPivStratFunctor

Functor storing state for tree-based mimicry pivoting.

Fields

• F::Vector{Int}: Candidate cluster node indices to search
• c::SVector{D,T}: Reference centroid used to bias selection
• tree::TreeType: Tree providing cluster geometry and membership
• pos::Vector{SVector{D,T}}: Point coordinates
• usedidcs::Vector{Int}: Selected global point indices (filled progressively)

(pivstrat::TreeMimicryPivotingFunctor)(npivot)

Select subsequent pivots by finding a cluster and then selecting the best point within that cluster based on mimicry pivoting strategy.

(pivstrat::TreeMimicryPivotingFunctor)()

Select the first pivot by locating a promising leaf cluster and choosing the point within that cluster that is closest to the reference centroid.

ValuePivStrat <: PivStrat

Abstract type for value-based pivoting strategies.

These strategies select pivots based on matrix element values sampled during the ACA algorithm. Most common approach for general matrices.

Concrete Types

• MaximumValue: Selects index with maximum absolute value (standard ACA)
• RandomSampling: Random selection (for statistical approaches)

ValuePivStratFunctor <: PivStratFunctor

Abstract type for stateful value-based pivoting functors.

iACA{RowPivType,ColPivType,ConvCritType}

Incomplete Adaptive Cross Approximation (iACA) compressor.

Unlike standard ACA, iACA computes only half of the factorization. It uses geometric pivoting strategies (e.g., mimicry or tree mimicry) to select row or column pivots based solely on spatial information, making it super efficient for hierarchical matrix construction where only row or column samples are requiered.

Fields

• rowpivoting::RowPivType: Strategy for selecting row pivots (geometric)
• columnpivoting::ColPivType: Strategy for selecting column pivots
• convergence::ConvCritType: Convergence criterion

(iaca::iACA{ValuePivStrat,TreeMimicryPivoting,ConvCrit})(rows, Ft, maxrank)

Initialize iACA functor for tree-based column pivoting. For hierarchical matrices where column selection uses tree-aware mimicry.

Arguments

• rows::AbstractVector{Int}: Row indices
• Ft::AbstractVector{Int}: Tree structure for column pivoting
• maxrank::Int: Maximum rank for approximation

(iaca::iACA{TreeMimicryPivoting,ValuePivStrat,ConvCrit})(Ft, cols, maxrank)

Initialize iACA functor for tree-based row pivoting. For hierarchical matrices where row selection uses tree-aware mimicry.

Arguments

• Ft::AbstractVector{Int}: Tree structure for row pivoting
• cols::AbstractVector{Int}: Column indices
• maxrank::Int: Maximum rank for approximation

(iaca::iACA{GeoPivStrat,ValuePivStrat,ConvCrit})(rows, cols)

Initialize iACA functor for row matrix compression with geometric row pivoting. Creates functors for geometric row pivoting and value-based column pivoting.

Arguments

• rows::AbstractVector{Int}: Row indices for geometric pivoting
• cols::AbstractVector{Int}: Column indices for geometric pivoting

(iaca::iACA{ValuePivStrat,GeoPivStrat,ConvCrit})(rows, cols)

Initialize iACA functor for column matrix compression with geometric column pivoting. Creates functors for value-based row pivoting and geometric column pivoting.

Arguments

• rows::AbstractVector{Int}: Row indices
• cols::AbstractVector{Int}: Column indices for geometric pivoting

(iaca::iACA{ValuePivStrat,MimicryPivoting,ConvCrit})(A, rowbuffer, colbuffer, maxrank; kwargs...)

Convenience method delegating to main computational routine for mimicry-based column pivoting.

Arguments

• A: Matrix to compress
• rowbuffer::AbstractArray{K}: Buffer for row data
• colbuffer::AbstractArray{K}: Buffer for column data
• maxrank::Int: Maximum rank
• rows: Row indices (optional keyword)
• cols: Column indices (optional keyword)
• rowidcs: Row index range (optional keyword)
• colidcs: Column index range (optional keyword)

(iaca::iACA{ValuePivStrat,TreeMimicryPivoting,ConvCrit})(A, rowbuffer, colbuffer, maxrank; kwargs...)

Convenience method delegating to main computational routine for tree-based column pivoting.

Arguments

• A: Matrix to compress
• rowbuffer::AbstractArray{K}: Buffer for row data
• colbuffer::AbstractArray{K}: Buffer for column data
• maxrank::Int: Maximum rank
• rows: Row indices (optional keyword)
• cols: Column indices (optional keyword)
• rowidcs: Row index range (optional keyword)
• colidcs: Column index range (optional keyword)

(iaca::iACA{MimicryPivoting,ValuePivStrat,ConvCrit})(A, colbuffer, rowbuffer, maxrank; kwargs...)

Convenience method delegating to main computational routine for mimicry-based row pivoting.

Arguments

• A: Matrix to compress
• colbuffer::AbstractMatrix{K}: Buffer for column data
• rowbuffer::AbstractMatrix{K}: Buffer for row data
• maxrank::Int: Maximum rank
• rows: Row indices (optional keyword)
• cols: Column indices (optional keyword)
• rowidcs: Row index range (optional keyword)
• colidcs: Column index range (optional keyword)

(iaca::iACA{TreeMimicryPivoting,ValuePivStrat,ConvCrit})(A, colbuffer, rowbuffer, maxrank; kwargs...)

Convenience method delegating to main computational routine for tree-based row pivoting.

Arguments

• A: Matrix to compress
• colbuffer::AbstractMatrix{K}: Buffer for column data
• rowbuffer::AbstractMatrix{K}: Buffer for row data
• maxrank::Int: Maximum rank
• rows: Row indices (optional keyword)
• cols: Column indices (optional keyword)
• rowidcs: Row index range (optional keyword)
• colidcs: Column index range (optional keyword)

iACA(tpos::Vector{SVector{D,F}}, spos::Vector{SVector{D,F}})

Construct an iACA compressor with default settings for geometric pivoting.

Creates an iACA using maximum value for row pivoting, mimicry pivoting for columns (mimicking the spatial distribution of a fully pivoting when selecting from spos), and Frobenius norm extrapolation for convergence.

Arguments

• tpos: Test/target point positions (reference distribution)
• spos: Source point positions (candidates for selection)

(iaca::iACA{ValuePivStratFunctor,GeoPivStratFunctor,ConvCritFunctor})(A, colbuffer, rowbuffer, maxrank, rows, cols, rowidcs)

Main computational routine for column matrix iACA (value-based row pivoting, geometric column pivoting). Performs incomplete ACA compression where columns are selected geometrically and rows by maximum value.

Arguments

• A: Matrix to compress
• colbuffer::AbstractArray{K}: Buffer for column data
• rowbuffer::AbstractArray{K}: Buffer for row data
• maxrank::Int: Maximum rank
• rows::Vector{Int}: Row indices storage
• cols::Vector{Int}: Column indices storage
• rowidcs::Vector{Int}: Row index range

Returns

• npivot::Int: Number of pivots computed
• rows::Vector{Int}: Selected row indices (global)
• cols::Vector{Int}: Selected column indices

(iaca::iACA{GeoPivStratFunctor,ValuePivStratFunctor,ConvCritFunctor})(A, colbuffer, rowbuffer, maxrank, rows, cols, colidcs)

Main computational routine for row matrix iACA (geometric row pivoting, value-based column pivoting). Performs incomplete ACA compression where rows are selected geometrically and columns by maximum value.

Arguments

• A: Matrix to compress
• colbuffer::AbstractMatrix{K}: Buffer for column data
• rowbuffer::AbstractMatrix{K}: Buffer for row data
• maxrank::Int: Maximum rank
• rows::Vector{Int}: Row indices storage
• cols::Vector{Int}: Column indices storage
• colidcs::Vector{Int}: Column index range

Returns

• npivot::Int: Number of pivots computed
• rows::Vector{Int}: Selected row indices
• cols::Vector{Int}: Selected column indices (global)

iFNormEstimator{F} <: ConvCrit

Frobenius norm-based convergence criterion for incomplete ACA (iACA). Uses moving average norm estimate for geometric pivoting scenarios.

Fields

• tol::F: Relative tolerance threshold

(cc::iFNormEstimator{F})()

Initialize iFNormEstimator functor with zero accumulated norm.

iFNormEstimatorFunctor{F} <: ConvCritFunctor

Stateful Frobenius norm estimator for iACA compression. Tracks moving average of row/column norms.

Fields

• normUV::F: Moving average norm
• tol::F: Relative tolerance threshold

(convcrit::iFNormEstimatorFunctor)(rcbuffer::AbstractVector{K}, npivot::Int)

Check convergence for iACA using moving average norm. Returns (npivot, continue) where continue is true if iteration should proceed.

Arguments

• rcbuffer::AbstractVector{K}: Current row or column buffer
• npivot::Int: Current pivot index

Returns

• npivot::Int: Final pivot count
• continue::Bool: Whether to continue iteration

(pivstrat::Union{Leja2Functor{D,F},FillDistanceFunctor{D,F}})()

Select the first point as the initial pivot.

Computes distances from all points to the first point and returns index 1.

aca(M; tol=1e-4, rowpivoting=MaximumValue(), columnpivoting=MaximumValue(),
    convergence=FNormEstimator(tol), maxrank=40, svdrecompress=false)

Compute adaptive cross approximation of matrix M returning low-rank factors.

High-level convenience function that automatically allocates buffers and returns U, V such that M ≈ U * V.

Arguments

• M::AbstractMatrix{K}: Matrix to approximate

Keyword Arguments

• tol::Real = 1e-4: Approximation tolerance
• rowpivoting = MaximumValue(): Row pivot selection strategy
• columnpivoting = MaximumValue(): Column pivot selection strategy
• convergence = FNormEstimator(tol): Convergence criterion
• maxrank::Int = 40: Maximum rank (hard limit)
• svdrecompress::Bool = false: Apply SVD-based recompression to reduce rank further

Returns

• U::Matrix{K}: Left factor, size (size(M,1), r) where r ≤ maxrank
• V::Matrix{K}: Right factor, size (r, size(M,2))

Satisfies M ≈ U * V with norm(M - U*V) / norm(M) ≲ tol (if maxrank sufficient).

SVD Recompression

When svdrecompress=true, performs QR-SVD recompression: computes M ≈ U*V, then U = Q*R, R*V = Û*Σ*V̂ᵀ, truncates small singular values, and returns optimal rank factors at the cost of additional computation.

acaᵀ(M; tol=1e-4, rowpivoting, columnpivoting, convergence, maxrank=40)

Convenience function for column-first ACA compression. Automatically allocates buffers and performs compression.

Arguments

• M::AbstractMatrix{K}: Matrix to compress
• tol: Convergence tolerance (default: 1e-4)
• rowpivoting: Row pivoting strategy (default: MaximumValueFunctor)
• columnpivoting: Column pivoting strategy (default: MaximumValueFunctor)
• convergence: Convergence criterion (default: FNormEstimator(0.0, tol))
• maxrank: Maximum rank (default: 40)

Returns

• colbuffer: Column factor (nrows × npivots)
• rowbuffer: Row factor (npivots × ncols)

findcluster(pivstrat, F, npivot)

Cluster-based selection used during later pivot iterations.

For each candidate cluster f in F, compute a composite score combining Leja products, fill distances and inverse-distance weights to the reference centroid; select the cluster maximizing this score and recurse until a leaf is reached.

findcluster(pivstrat, F)

Find a leaf cluster (node) that best matches the reference centroid.

Traverses the tree greedily by choosing child clusters whose centers are closest (in weighted inverse-distance sense) to the reference centroid pivstrat.c. Returns a node index whose firstchild is zero (leaf) or recurses into children.

leja2!(pivstrat::GeoPivStratFunctor, nextidx::Int)

Update minimum distances after selecting pivot nextidx.

Computes distances from all points to the newly selected pivot and updates the minimum distance vector h by taking element-wise minimum with new distances. This shared helper is used by both Leja2 and fill distance strategies.

Arguments

• pivstrat::GeoPivStratFunctor: Functor with distance vector to update
• nextidx::Int: Index of newly selected pivot

nextrc!(buf, A::AbstractArray, i, j)

Fill buffer buf with submatrix A[i, j].

Internal utility for matrix element access. Can be extended for custom matrix types to enable ACA compression of matrix-free operators.

normF!(convcrit::ConvCritFunctor, rowbuffer, colbuffer, npivot, maxrows, maxcolumns)

Update Frobenius norm estimate for standard ACA. Incrementally computes squared norm of UV factorization using current pivot and all previous pivots.

Arguments

• convcrit::ConvCritFunctor: Convergence criterion functor to update
• rowbuffer::AbstractMatrix{K}: Row factor buffer
• colbuffer::AbstractMatrix{K}: Column factor buffer
• npivot::Int: Current pivot index
• maxrows::Int: Number of active rows
• maxcolumns::Int: Number of active columns

normF!(convcrit::ConvCritFunctor, rcbuffer::AbstractVector{K}, npivot::Int)

Update running norm estimate for incomplete ACA (iACA). Computes moving average of row/column norms across pivots.

Arguments

• convcrit::ConvCritFunctor: Convergence criterion functor to update
• rcbuffer::AbstractVector{K}: Current row or column buffer
• npivot::Int: Current pivot index

tolerance(cc::FNormExtrapolatorFunctor)

Get tolerance from underlying estimator.

tolerance(cc::RandomSamplingFunctor)

Get tolerance from random sampling functor.

tolerance(cc::iFNormEstimatorFunctor)

Get tolerance threshold from iACA estimator functor.

tolerance(cc::FNormEstimator)

Get tolerance threshold from estimator.