API Reference

assemble(op, testspace, trialspace; tree=..., quadstrat=..., kwargs...)

Assemble a hierarchical matrix with automatic tree-based blocking.

High-level convenience function that automatically constructs a hierarchical clustering tree and assembles the complete HMatrix with near and far-field blocks. This is the recommended entry point for most applications.

Arguments

• op: Operator/kernel for matrix entry evaluation

• testspace: Test space (row basis/points)

• trialspace: Trial space (column basis/points)

• tree: Hierarchical tree structure. Auto-generated from AdaptiveCrossApproximation.defaulttreebackend() if not provided: a H2Trees.TwoNTree when only H2Trees.jl is loaded, or a k-means clustered tree when ParallelKMeans.jl is loaded alongside it.

• treekwargs: Keyword arguments forwarded to the automatic tree construction (e.g. minvalues, numberofclusters for the k-means backend); ignored if tree is given explicitly.

• quadstrat: Quadrature strategy, matching BEAST.assemble's keyword of the same name. Defaults like BEAST.defaultquadstrat(op, testspace, trialspace) for BEAST operators (via the ACABEAST extension).

• nearquadstrat: Quadrature strategy for near-field (dense) blocks. Defaults to quadstrat.

• farquadstrat: Quadrature strategy for far-field (compressed, admissible) blocks. Defaults to tofarquadstrat(quadstrat), which strips singular-quadrature handling since far blocks are always well-separated.

• kwargs...: Additional parameters passed to HMatrix:

  • tol: Convergence tolerance (default 1e-4); also governs every later recompression of the hierarchical arithmetic
  • maxrank: Maximum rank for compression (default 40)
  • compressor: ACA-style compressor. The default is selected by defaultcompressor(op, testspace, trialspace; tol) and is usually ACA.
  • isnear: Admissibility predicate (default isnear())
  • spaceordering: Space ordering strategy (default PreserveSpaceOrder())
  • ntasks: Number of parallel assembly tasks (default Threads.nthreads())
  • verbose: Enable progress output (default true)

Returns

• HMatrix: Assembled hierarchical matrix

Notes

Requires H2Trees.jl to be loaded for automatic tree generation. If providing a custom tree, ensure it implements the tree interface expected by HMatrix assembly. The two-space call uses general assembly even when testspace === trialspace. For a transpose-symmetric operator, use assemble(op, space; kwargs...) to select symmetric assembly explicitly. For operators whose matrix is cheap to build directly and never benefits from low-rank compression (e.g. BEAST's local operators Identity/NCross), the ACABEAST extension adds a more specific assemble method that bypasses tree construction and ACA entirely, calling BEAST.assemble directly.

Examples

# With BEAST boundary integral operators
hmat = AdaptiveCrossApproximation.assemble(op, testspace, trialspace; tol=1e-5, maxrank=100)
y = hmat * x  # Efficient matrix-vector product

See also

HMatrix

assemble(op, space; tree=..., quadstrat=..., kwargs...)

Assemble a transpose-symmetric H-matrix on one space. Automatic tree construction builds one shared cluster tree. With an explicit tree, only its test cluster tree is used for both axes.

The operator and any custom isnear predicate must be transpose-symmetric; this is a caller-supplied assumption and is not checked. Opposite off-diagonal blocks use a transpose, without complex conjugation. Diagonal near blocks are assembled in full and symmetrized. Each unordered far-field pair is compressed once with the configured compressor.

Accepts the tree, quadrature, compression, ordering, and ntasks keywords of the two-space overload. The call assemble(op, space, space) uses general assembly. BEAST local operators such as Identity and NCross are assembled directly.

Examples

hmat = AdaptiveCrossApproximation.assemble(op, space; tol=1e-5)
hmat = AdaptiveCrossApproximation.assemble(op, space; tree=tree, tol=1e-5)

See also

HMatrix

AdaptiveCrossApproximation

Adaptive Cross Approximation (ACA) algorithms for hierarchical low-rank matrix compression.

Provides standard and incomplete adaptive cross approximation algorithms optimized for boundary integral operators and other kernel-based matrices. Key features:

• ACA: Standard adaptive cross approximation selecting pivots by alternating rows/columns
• IACA: Incomplete variant for geometric pivoting in hierarchical matrix construction
• HMatrix: Hierarchical matrix representation combining dense near-field and low-rank far-field blocks
• Pivoting strategies: Maximum value, geometric (Leja, Fill Distance, Mimicry), random sampling
• Convergence criteria: Frobenius norm estimation, random sampling, extrapolation, combined criteria
• Kernel matrices: Support for BEAST boundary integral operators and point-based kernels

Main API

Compressors:

• ACA: Standard row-first variant
• ACAᵀ: Column-first variant (dual of ACA)
• IACA: Incomplete variant for geometric pivoting and hierarchical matrices
• aca: Convenience function for matrix compression

Hierarchical matrices:

• HMatrix: Hierarchical matrix type
• AdaptiveCrossApproximation.assemble: Automatic assembly with tree-based blocking
• nearmatrix, farmatrix: Extract system components

Pivoting strategies:

• MaximumValue: Partial pivoting (largest absolute value)
• Leja2: Modified Leja point selection
• FillDistance: Geometric fill distance minimization
• MimicryPivoting: Distributional mimicry without full matrix access
• TreeMimicryPivoting: Tree-aware variant for H²-matrices

Convergence criteria:

• FNormEstimator: Frobenius norm-based stopping (ACA and IACA paths)
• FNormExtrapolator: Extrapolation-enhanced convergence detection
• PhaseExtrapolator: Multi-phase extrapolation for geometric pivoting
• RandomSampling: Random sampling-based convergence

Kernel matrices:

• AbstractKernelMatrix: Interface for lazy matrix entry evaluation
• PointMatrix: Point cloud kernel matrices
• BEASTKernelMatrix: BEAST boundary integral operator matrices

Example

using AdaptiveCrossApproximation

# Compress a matrix with default settings
U, V = aca(M; tol=1e-4, maxrank=50)
approx = U * V

# Or build an HMatrix with automatic tree-based blocking
hmat = AdaptiveCrossApproximation.assemble(operator, testspace, trialspace)
y = hmat * x  # Matrix-vector product

See also

• BEAST.jl for boundary integral operators
• H2Trees.jl for hierarchical clustering
• H2Trees.jl for hierarchical block partitioning

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(; tol=1e-4, rowpivoting=MaximumValue(), columnpivoting=MaximumValue(),
    convergence=FNormEstimator(tol))

Build an ACA compressor from keyword arguments.

This is the constructor most users call directly (e.g. ACA(tol=1e-4) or ACA(rowpivoting=Leja2(pos))); convergence defaults to FNormEstimator(tol) so passing tol alone is usually enough.

Keyword Arguments

• tol::Real = 1e-4: Tolerance used to build the default convergence criterion. Ignored if convergence is passed explicitly.
• rowpivoting = MaximumValue(): Row pivot selection strategy.
• columnpivoting = MaximumValue(): Column pivot selection strategy.
• convergence = FNormEstimator(tol): Convergence criterion to stop iterations.

(aca::ACA{FullPivoting,FullPivoting,FNormEstimator})(A, maxrank=min(size(A)...); sampled=false)

Compute a full-pivoting ACA factorization of the dense matrix A, in place.

At each step, selects the entry of largest absolute value in the remaining (unfactored) submatrix as the next pivot, swaps it onto the diagonal, and eliminates it with a rank-1 Schur update — the direct, whole-matrix counterpart of MaximumValue-based ACA. Used wherever the whole matrix is available up front, e.g. as the CPU reference for the batched GPU kernel in the ACACUDA extension.

With sampled=true, stops when norm(residual)/norm(original) * sqrt(s/(s-rank)) <= tol, where s is the sampled column count. This estimates the full block's relative Frobenius error assuming representative remaining residual entries and a far field much larger than the sample. Pivot rows cancel because all rows are sampled. The default sampled=false uses the ordinary relative Frobenius criterion.

Arguments

• A::AbstractMatrix{T}: matrix to factor; overwritten in place with the working Schur-complement state.
• maxrank::Int: hard cap on the number of pivots.
• sampled::Bool: rescale the residual of representative column samples.

Returns

• rank::Int: number of pivots selected (≤ maxrank).
• rowpivots::Vector{Int}, colpivots::Vector{Int}: selected row/column indices, in selection order.

(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. Previously computed rank-one terms are subtracted from every newly sampled row and column.

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ᵀ(; tol=1e-4, rowpivoting=MaximumValue(), columnpivoting=MaximumValue(),
    convergence=FNormEstimator(tol))

Build an ACAᵀ compressor from keyword arguments.

This is the constructor most users call directly, mirroring ACA's keyword constructor; convergence defaults to FNormEstimator(tol) so passing tol alone is usually enough.

Keyword Arguments

• tol::Real = 1e-4: Tolerance used to build the default convergence criterion. Ignored if convergence is passed explicitly.
• rowpivoting = MaximumValue(): Row pivot selection strategy.
• columnpivoting = MaximumValue(): Column pivot selection strategy.
• convergence = FNormEstimator(tol): Convergence criterion to stop iterations.

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

Compute column-first 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. Previously computed rank-one terms are subtracted from every newly sampled column and row.

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, :]

AbstractKernelMatrix{T}

Abstract matrix-like interface for kernel-based entry evaluation used by ACA-style compressors.

Arguments

• T: scalar element type returned by kernel evaluations

Returns

A subtype that supports lazy matrix entry access through the kernel matrix interface.

Notes

Implement this type when matrix entries are computed on demand from geometric/operator data. A concrete backend should implement size(matrix) and matrix(block, rows, columns); nextrc! uses that callable interface to sample rows and columns without materializing the full matrix.

See also

AbstractKernelMatrix(operator, testspace, trialspace; args...)

AbstractKernelMatrix(operator, testspace::AbstractVector, trialspace::AbstractVector; args...)

Create a PointMatrix kernel wrapper from vector point data and operator.

Constructs a PointMatrix when given vector collections of test and trial points. Matches the exported AbstractKernelMatrix factory interface to provide point-based kernel evaluation.

Arguments

• operator: kernel function or operator
• testspace::AbstractVector: test point locations (indexed collection)
• trialspace::AbstractVector: trial point locations (indexed collection)
• args...: additional keyword arguments (unused for point-based evaluation)

Returns

• PointMatrix with element type inferred from operator

AbstractKernelMatrix(operator, testspace, trialspace; args...)

Construct a concrete kernel matrix wrapper from operator and space data.

Arguments

• operator: operator or kernel definition
• testspace: space for row evaluation points or basis data
• trialspace: space for column evaluation points or basis data
• args...: backend-specific keyword arguments

Returns

A concrete subtype of AbstractKernelMatrix provided by method dispatch.

Notes

This declaration defines the interface entry point. Concrete backends provide specialized methods for specific operator/space types.

See also

AbstractKernelMatrix, nextrc!

AbstractKernelMatrix(operator::Function, testspace::AbstractVector, trialspace::AbstractVector; args...)

Create a PointMatrix from a plain Julia function kernel (with warning).

Provides fallback support for plain function kernels. Issues a warning as operators with structure (kernels, boundary integral operators) are typically preferred for better performance and correctness.

Arguments

• operator::Function: plain Julia function with signature operator(testpoint, trialpoint)
• testspace::AbstractVector: test point locations (indexed collection)
• trialspace::AbstractVector: trial point locations (indexed collection)
• args...: additional keyword arguments (unused)

Returns

• PointMatrix with element type inferred from function evaluation

AdditionWorkspace(C::HMatrixCore, A::HMatrixCore; ntasks=Threads.nthreads())

Buffers for axpy!(α, A, C, workspace) and axpby!(α, A, β, C, workspace). Reusable for every pair of matrices with the same partitions as C and A. The blocks are updated on ntasks parallel tasks; ntasks=1 runs on the calling task.

BEASTKernelMatrix{T,NearBlockAssemblerType} <: AbstractKernelMatrix{T}

Kernel matrix wrapper for BEAST operator assembly.

Provides lazy matrix entry evaluation through a BEAST block assembler, which computes matrix entries on demand from operator and basis-function data.

Fields

• nearassembler::NearBlockAssemblerType: BEAST assembler providing matrix entries

Type parameters

• T: scalar element type returned by kernel evaluations
• NearBlockAssemblerType: type of the underlying BEAST assembler

BlockCSC{I}

Column-wise (CSC) traversal of the terminal blocks. The terminals of column cluster σ are colptr[σ]:(colptr[σ + 1] - 1), with row clusters rownodes[j]; csrmap[j] points into the canonical BlockCSR entries, so no block is stored twice.

BlockCSR{I}

Canonical row-wise (CSR) index of the terminal blocks of an H-matrix. The terminals of row cluster τ are the entries rowptr[τ]:(rowptr[τ + 1] - 1), sorted by column cluster colnodes[k]. isfar[k] selects the storage vector (far or near) and storageidx[k] the position of the block in it. transposed[k] marks an entry that applies the transpose of a block stored for the opposite orientation (symmetric storage only).

BlockScratch{T}()

Reusable temporary storage of one task for low-rank block arithmetic. The buffers start empty, grow on demand and never shrink; their layout is private to the kernels. Final numerical blocks never reference scratch storage.

CombinedConvCrit

Composite convergence criterion combining multiple criteria. Stops only when ALL constituent criteria have signaled convergence (AND logic).

Fields

• crits::Vector{ConvCrit}: Vector of convergence criteria to combine

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

ConvCrit

Abstract base type for convergence criteria used by ACA and IACA compressors.

Notes

Concrete subtypes define how stopping decisions are made and are converted into stateful ConvCritFunctor objects during block compression.

See also

ConvCritFunctor, FNormEstimator, FNormExtrapolator, PhaseExtrapolator, RandomSampling

ConvCritFunctor

Abstract base type for stateful convergence criterion functors.

Notes

Instances are called during ACA iterations and return (npivot, continue::Bool). Subtypes should implement reset! to reinitialize internal state for a new block.

See also

ConvCrit, reset!, normF!

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

• AdaptiveCrossApproximation.RandomSamplingPivoting: Selects pivots from convergence samples

ConvPivStratFunctor <: PivStratFunctor

Abstract type for stateful convergence-driven pivoting functors.

DenseLeafLU <: LinearAlgebra.Factorization
leaflu!(A; node=0, check=true, checkfinite=true)
leaflu!(F::DenseLeafLU; check=true, checkfinite=true)

Pivoted LU P*A = L*U (unit-diagonal L) of a square dense diagonal leaf, in place: F.factors === A. The second form factorizes new values written into F.factors, reusing the pivot storage. ipiv holds LAPACK's sequence of local row swaps. info == 0 means success, a positive info a zero pivot, which throws a LeafLUFailure unless check=false; info == -1 marks an invalid state. checkfinite=false skips the scan for nonfinite input.

EFIEDirectionalFilter

EFIE direction/orientation PivotingFilter for TreeMimicryPivoting. Restricts descent and pivot selection to basis functions of the currently active direction, cycling through directions in phases. Pass it to the four-argument TreeMimicryPivoting(refpos, pos, tree, filter) constructor.

Fields

• edgedirections::Vector{Int32}: per-index edge-direction group id
• basisdirections::Vector{Int32}: per-index normal-direction group id
• nodedirectionids::Vector{Vector{Int32}}: dominant direction ids per tree node

EFIEDirectionalFilterState{CC}

Per-factorization state of an EFIEDirectionalFilter: the shared convergence criterion plus the set of directions whose phase has finished.

FNormEstimator{F} <: ConvCrit

Frobenius norm-based convergence criterion for ACA and IACA.

Dispatches on input type: matrix arguments follow the ACA path (accumulated Frobenius norm), vector arguments follow the IACA path (moving-average norm).

Fields

• tol::F: Relative tolerance threshold

FNormExtrapolator{F} <: ConvCrit

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

Fields

• estimator::FNormEstimator{F}: Underlying norm estimator

FNormExtrapolator(tol::F)

Construct extrapolator with Frobenius norm estimator.

Arguments

• tol::F: Convergence tolerance

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

FullPivoting <: ValuePivStrat

Pivoting strategy that selects the entry of maximum absolute value across the entire remaining (unfactored) submatrix.

Unlike MaximumValue, which only searches a single sampled row or column, full pivoting requires the whole matrix to be available up front: see the ACA{FullPivoting,FullPivoting,FNormEstimator} callable in fullpivotedaca.jl, which has no nextrc!-based partial-sampling path, and its batched GPU counterpart in the ACACUDA extension.

GPUBEASTKernelMatrix{T,NearBlockAssemblerType,FunctorsType} <: AbstractKernelMatrix{T}

GPU-accelerated kernel matrix wrapper for BEAST operator assembly.

Analogous to BEASTKernelMatrix, but backed by a GPU near-field block assembler. Built automatically by AdaptiveCrossApproximation.beastkernelmatrix when GPUMatrixData is passed as matrixdata; requires the ACABEASTCUDA package extension to be loaded.

Fields

• nearassembler::NearBlockAssemblerType: functors[1], used for single-block sampling (the per-block call operator / classic ACA pivoting via nextrc!), which is inherently single-device
• functors::FunctorsType: one GPU-backed BEAST assembler per device (length 1 for ndevices == 1); used by the batched assemble_blocks path, which parallelizes across all of them

Type parameters

• T: scalar element type returned by kernel evaluations
• NearBlockAssemblerType: type of nearassembler (a single device's assembler)
• FunctorsType: type of functors (a vector of per-device assemblers)

GPUMatrixData{QuadStratType}

Configuration for GPU-accelerated BEAST kernel matrix assembly.

Passed as the matrixdata keyword argument to AbstractKernelMatrix to build a GPUBEASTKernelMatrix instead of a plain BEASTKernelMatrix; requires the ACABEASTCUDA package extension to be loaded (BEAST.jl and CUDA.jl available).

Experimental: GPU assembly also needs BEAST's BEASTCUDAExt, which released BEAST versions do not provide yet. Without it, building the kernel matrix throws an ArgumentError.

Physical device selection is automatic: unless devices is given explicitly, the extension picks ndevices currently-idle GPUs (no active compute processes) at AdaptiveCrossApproximation.beastkernelmatrix build time. Devices are dispatched via OhMyThreads.@tasks (ntasks == ndevices), so ndevices is not tied to Threads.nthreads() - CPU-side code is free to use more threads than there are devices; with fewer Julia threads than ndevices, devices simply lose some overlap rather than erroring.

Fields

• quadstrat::QuadStratType: BEAST quadrature strategy used to assemble matrix entries
• ndevices::Int: Number of GPU devices to use. When devices is given, defaults to length(devices); otherwise defaults to 1. Passing it explicitly alongside devices is allowed only if it matches length(devices).
• devices::Union{Nothing,Vector{Int}}: Explicit CUDA device ids to pin to, bypassing automatic free-device selection; nothing (default) means auto-select

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: Selects the point farthest from the current pivot set

GeoPivStratFunctor <: PivStratFunctor

Abstract type for stateful geometric pivoting functors.

H2Tree <: AbstractTree

Tree backend marker selecting H2Trees.jl's TwoNTree clustering, built by the ACAH2Trees extension.

HMatrix

Compatibility alias for HMatrixCore.

HMatrix(operator, testspace, trialspace, tree; kwargs...)

Assemble a hierarchical matrix approximation of an operator on test and trial spaces.

Arguments

• operator: bilinear form or kernel operator used for matrix entry evaluation
• testspace: test space used for row indexing
• trialspace: trial space used for column indexing
• tree: hierarchical clustering/tree structure controlling block partitioning
• tol: compression tolerance (default 1e-4). It is stored with the matrix and governs every later recompression of the hierarchical arithmetic.
• compressor: ACA-style compressor. Defaults to defaultcompressor(operator, testspace, trialspace; tol).
• isnear: near-field predicate controlling admissibility
• maxrank: maximum rank for far-field block compression
• spaceordering: strategy for applying tree permutations to spaces
• nearmatrixdata: optional data passed to near-field assembly
• farmatrixdata: optional data passed to far-field assembly
• ntasks: number of parallel assembly tasks (default Threads.nthreads())
• verbose: enable progress output for near- and far-field assembly (default true)

Returns

An HMatrix containing assembled near and far interactions.

Notes

Use this constructor as the main entry point when you already have a tree. For a convenience entry point, use assemble. This two-space constructor uses general assembly even when the spaces are the same object. Use HMatrix(operator, space, tree; kwargs...) for a transpose-symmetric operator.

See also

assemble, ACA, IACA, farmatrix, nearmatrix

HMatrix(operator, space, tree; kwargs...)

Assemble a transpose-symmetric H-matrix on one space. Only testtree(tree) is used for both axes. The operator and any custom isnear predicate must be transpose-symmetric; this assumption is not checked. Complex symmetric operators use a transpose, without conjugation, for the opposite block.

Each terminal near pair is stored as one dense block. Far blocks use the configured compressor once per unordered pair and share their factors with the transposed logical block. Diagonal near blocks are assembled in full, then made symmetric by copying their upper triangles into their lower triangles.

Compression, assembly-data and ntasks keywords follow the two-space constructor. For automatic tree construction, use assemble(operator, space).

Examples

hmat = HMatrix(operator, space, tree; tol=1e-5)

HMatrixBlock{T}

Non-owning rectangular block rows × cols of a _TreeView, in tree order. entries lists the CSR entries of the terminal blocks that meet the block; terminals crossing its border are clipped to it by the operations that use it. Hierarchical blocks are the operands of the internal products, sums and triangular solves. Construct them with blockview.

HMatrixComponent{T,H,Far}

Lazy near-field (Far = false) or far-field (Far = true) part of an H-matrix, returned by nearmatrix and farmatrix. It shares the blocks of its parent and supports Matrix and products, also through a MatVecWorkspace.

HMatrixCore{T}

Hierarchical matrix with a retained block tree, separate dense and low-rank storage, canonical CSR block ordering, and a CSC traversal map.

tol is the relative accuracy chosen at assembly. Every later recompression (products, sums, recompress! and lu) truncates each block to this tolerance; for operands with different tolerances the larger one is used.

The struct is immutable and operations never change the blocks of their inputs. Only the documented in-place operations overwrite a matrix: the destination of mul!(C, A, B, α, β), axpy!, axpby!, rmul! and lmul!, and the argument of lu! and recompress!.

HMatrixLU <: Factorization

Hierarchical LU factorization P*A ≈ L*U returned by lu and lu!. P is the product of the row permutations inside the dense diagonal leaves. The factors live in the blocks of the factorized matrix. Solve with F \ b, ldiv!(F, b) or ldiv!(x, F, b), also with transpose(F) and F', for vectors and matrices of right-hand sides. F is read-only during solves: concurrent solves with one factorization each use their own SolveWorkspace.

converged, rank_limited, max_block_error and flushes summarize the local recompressions of the factorization, not a global error bound.

HMatrixTriangular(W::_TreeView, leaves; uplo=:lower)
HMatrixTriangular(parent::HMatrixTriangular; node)

Lower (unit diagonal) or upper triangular factor of P*A = L*U on a view whose dense diagonal terminals hold the packed LAPACK factors of the leaf LUs (leaves, see DenseLeafLU). Both factors share the same view; L reads the strictly lower and U the upper part of each leaf. The diagonal terminals must cover the diagonal without gaps, and no other terminal may cross it. The row pivots are applied separately with _pivot!.

The off-diagonal blocks between sibling clusters are stored as panels with column (leftptr) and row (rightptr) adjacency, so a solve can subtract the contributions of a solved cluster from the clusters still to be solved. The second form selects the factor of the diagonal cluster node, sharing the panels and maps of parent.

IACA{RowPivType,ColPivType,ConvCritType}

Incomplete Adaptive Cross Approximation (IACA) compressor.

Unlike standard ACA, IACA computes only one side per iteration and relies on geometric pivoting strategies (for example mimicry or tree mimicry) to select pivots from spatial information. This reduces matrix entry evaluations in hierarchical matrix construction, where only selected row or column samples are required. One pivoting direction must be geometric and the other value-based; the algorithm returns the selected row and column indices rather than a materialized low-rank factorization.

Fields

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

IACA(tpos, spos)

Create a default incomplete ACA compressor for geometrically indexed row/column sets.

Arguments

• tpos::Vector{SVector{D,F}}: geometric positions for test indices
• spos::Vector{SVector{D,F}}: geometric positions for trial indices

Returns

An IACA instance using MaximumValue for rows, MimicryPivoting for columns, and FNormExtrapolator for convergence.

See also

IACA, MimicryPivoting, FNormExtrapolator

iaca(A, colbuffer, rowbuffer, rowpivots, colpivots, rowidcs, maxrank)

Low-level IACA iteration with value-based row pivoting and geometric column pivoting. This method operates on a stateful compressor built for a particular index block.

Arguments

• A: Matrix to compress
• colbuffer::AbstractArray{K}: Buffer for column data
• rowbuffer::AbstractArray{K}: Buffer for row data
• rowpivots::Vector{Int}: Storage for selected row indices
• colpivots::Vector{Int}: Storage for selected column indices
• rowidcs::Vector{Int}: Row index range
• maxrank::Int: Maximum number of pivots

Returns

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

iaca(A, colbuffer, rowbuffer, rowpivots, colpivots, colidcs, maxrank)

Low-level IACA iteration with geometric row pivoting and value-based column pivoting. This method operates on a stateful compressor built for a particular index block.

Arguments

• A: Matrix to compress
• colbuffer::AbstractMatrix{K}: Buffer for column data
• rowbuffer::AbstractMatrix{K}: Buffer for row data
• rowpivots::Vector{Int}: Storage for selected row indices
• colpivots::Vector{Int}: Storage for selected column indices
• colidcs::Vector{Int}: Column index range
• maxrank::Int: Maximum number of pivots

Returns

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

IdentityPermutation

Zero-storage marker indicating that an axis is already in tree order.

IsNearFunctor{F,CrossLevel}

Geometric admissibility functor with separation parameter η and cross-level traversal encoded as a Boolean type parameter. Symmetry is selected by the interaction traversal function.

KMeansTreeBackend <: AbstractTree

Tree backend marker selecting k-means clustering (via ParallelKMeans.jl), built by the ACAParallelKMeansTrees extension.

LUWorkspace(H::HMatrixCore; batchrank=128, ntasks=Threads.nthreads())
LUWorkspace(workspace::LUWorkspace)

Plans and buffers of the hierarchical LU factorization. The workspace analyses the partition of H once: it builds the elimination schedule, every triangular solve and Schur-complement product plan, and the dependency graph between their block operations. It is not bound to H: lu!(A, workspace) factorizes any matrix A with the same cluster tree and block partition (ranks may differ), for example the matrices of a frequency sweep on one geometry, without planning again.

The factorization runs on ntasks parallel tasks. Every block operation starts as soon as the blocks it reads are final, and the factors do not depend on ntasks; ntasks=1 runs on the calling task. With ntasks > 1, use a single BLAS thread (BLAS.set_num_threads(1)). batchrank bounds the pending update columns per far block. One workspace serves one factorization at a time; LUWorkspace(workspace) plans a second one for concurrent factorizations.

LeafLUFailure(node, pivot)

An exactly zero pivot was encountered in a dense diagonal leaf. node is the caller-supplied cluster ID (zero if unspecified); pivot is local to the leaf. Leaf-restricted pivoting cannot repair a singular leaf using rows outside it.

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

Geometric pivoting strategy based on modified Leja points.

After the first point, each pivot maximizes its minimum distance to the points selected so far. This produces a well-separated sequence and is referred to as Leja2 pivoting 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

LowRankMatrix{T}

Low-rank numerical block represented by factors U and V. Temporary multiplication storage deliberately does not belong to the block. The block is mutable so arithmetic can replace its factors when its rank changes.

MatVecWorkspace(H::HMatrixCore; ntasks=Threads.nthreads())
MatVecWorkspace(workspace::MatVecWorkspace)

Matrix-vector product operator for H. It holds H, a precomputed parallel schedule and the internal buffers of the product, and can be used wherever H is used as a linear map:

A = AdaptiveCrossApproximation.MatVecWorkspace(H)
mul!(y, A, x)                 # y = H*x
mul!(y, transpose(A), x, α, β)
Y = A' * X                    # several right-hand sides at once

Vectors are in the original (external) ordering. The workspace owns its buffers: repeated products with the same number of columns do not allocate numerical storage, and the work of one product is distributed over ntasks parallel tasks (ntasks=1 runs on the calling task). One workspace serves one product at a time. For concurrent products, give each task its own copy with MatVecWorkspace(workspace); copies share the schedule and H. Products with H itself build a temporary workspace on every call.

A real matrix also multiplies complex vectors. The adjoint product of a complex matrix uses the conjugated transpose product.

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.

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

(pivstrat::MimicryPivotingFunctor)(npivot::Int)

Select the npivot-th pivot by index count rather than residual data, as used by IACA.

Returns the global index of the pivot, i.e. an entry of the idcs the functor was built with. The first pivot is the candidate closest to the reference centroid; the selection is the one TreeMimicryPivoting makes within a single leaf.

NoFilter

Identity PivotingFilter: accepts every node and index and runs a single directionless phase, recovering the plain (unfiltered) pivoting behaviour. It is the default filter of TreeMimicryPivoting.

NoFilterState

Per-factorization state of NoFilter; stateless. Inherits every hook from the PivotingFilterState identity defaults.

PermuteSpaceInPlace <: SpaceOrderingStyle

spaceordering style that permutes testspace/trialspace in place to match the tree's internal point ordering, rather than leaving them untouched.

Pass as HMatrix(...; spaceordering=PermuteSpaceInPlace()). Useful when downstream code expects a space physically reordered to tree order; compare with the default PreserveSpaceOrder.

The single-space call ordering(tree, space) uses only testtree(tree) and permutes the space once. Both general and transpose-symmetric HMatrix assembly support this ordering.

PhaseExtrapolator{F} <: ConvCrit

Convergence criterion using polynomial extrapolation of pivot norms across multiple phases.

Extends FNormExtrapolator with per-phase direction tracking. A pivot satisfies the criterion when the global and current-phase histories extrapolate below the requested tolerance. Stopping requires two consecutive pivots that satisfy the criterion.

Fields

• estimator::FNormEstimator{F}: Underlying norm estimator

See also

FNormExtrapolator, PhaseExtrapolatorFunctor, reset_phase!

PhaseExtrapolatorFunctor{F} <: ConvCritFunctor

Stateful functor for PhaseExtrapolator.

Tracks per-pivot norms and their associated phases, fitting a quadratic polynomial to predict convergence. Requires two consecutive converging pivots before stopping.

Fields

• estimator::FNormEstimatorFunctor{F}: Moving-average norm state
• lastnorms::Vector{F}: Per-pivot norms, indexed by pivot number
• normdirections::Vector{Int32}: Phase label for each pivot
• lastconverged::Bool: Whether the previous pivot also converged
• currentdirection::Int32: Phase label currently active (set via reset_phase!)

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

PivotingFilter

Abstract supertype for pivot filters. A concrete filter is an immutable descriptor holding the data that restricts pivot selection (e.g. per-index orientation ids); it is paired with a PivotingFilterState built once per factorization.

Currently consumed only by TreeMimicryPivoting; the interface hooks are written against the abstract PivStratFunctor so they can later be generalized to other strategies.

See also NoFilter, EFIEDirectionalFilter.

PivotingFilterState

Abstract supertype for the mutable per-factorization state of a PivotingFilter. The identity hooks defined on this type make an un-overridden filter behave like NoFilter: every node/index is accepted, no edge weighting is applied, and a single directionless phase runs. A concrete filter overrides only the hooks whose behaviour differs from the identity.

PointMatrix{T,FunctorType,PointCollectionType} <: AbstractKernelMatrix{T}

Kernel matrix evaluating entries from a kernel functor and point collections.

Stores point sample locations and a kernel function, computing matrix entries on demand by evaluating the kernel at test and trial point pairs. Useful for point cloud interactions or problems with explicit coordinate data.

Fields

• functor::FunctorType: Kernel function or operator to evaluate
• testpoints::PointCollectionType: Test space point locations
• trialpoints::PointCollectionType: Trial space point locations

Type parameters

• T: scalar element type returned by kernel evaluations
• FunctorType: type of the kernel functor
• PointCollectionType: type of point collections (e.g., Vector, AbstractArray)

PreserveSpaceOrder <: SpaceOrderingStyle

spaceordering style that leaves testspace/trialspace untouched; block assembly indexes through the tree's permutation instead. This is the default for HMatrix(...; spaceordering=PreserveSpaceOrder()). Compare with PermuteSpaceInPlace.

The single-space call ordering(tree, space) returns the space unchanged.

ProductWorkspace(C::HMatrixCore, A::HMatrixCore, B::HMatrixCore;
                 batchrank=128, ntasks=Threads.nthreads())

Plan and buffers for mul!(C, A, B, α, β, workspace). Reusable for every triple of matrices with the same partitions as C, A and B. The blocks of C are updated on ntasks parallel tasks; the result does not depend on ntasks, and ntasks=1 runs on the calling task. batchrank bounds the pending update columns per far block.

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

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)

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 the random-sampling convergence functor to provide statistically based pivot selection.

Fields

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

RecompressionWorkspace(H::HMatrixCore; ntasks=Threads.nthreads())

Buffers for recompress!(H, workspace). The blocks are recompressed on ntasks parallel tasks; ntasks=1 runs on the calling task.

SolveWorkspace(F::HMatrixLU)
SolveWorkspace(workspace::SolveWorkspace)

Buffers for solves with the factorization F. It acts like F: ldiv!(S, b), ldiv!(x, S, b), S \ b, ldiv!(transpose(S), b) and ldiv!(S', b), for vectors and matrices of right-hand sides. Solves with F itself build a temporary workspace on every call. One workspace serves one solve at a time; SolveWorkspace(workspace) gives another task its own.

SpaceOrderingStyle

Abstract type selecting how test/trial spaces are reconciled with a tree's internal point ordering during HMatrix assembly.

Concrete Types

• PreserveSpaceOrder: Leave spaces untouched, index through the tree's permutation instead (the default).
• PermuteSpaceInPlace: Physically permute spaces to match tree order.

TreeMimicryPivoting{D,T,TreeType,Filter} <: 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.

A pluggable PivotingFilter restricts the tree descent and the pivot selection. The default NoFilter accepts every node and index, recovering the plain geometric strategy. EFIEDirectionalFilter groups basis functions by orientation and rotates through them in phases.

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 providing cluster centers, children and values
• filter::Filter: Restriction on descent and pivot selection

Type parameters

• D: spatial dimension
• T: numeric type for coordinates
• TreeType: tree adapter (must implement center, values, children, firstchild)
• Filter: filter type, statically dispatched in the per-pivot hot loops

TreeMimicryPivoting(refpos, pos, tree)
TreeMimicryPivoting(refpos, pos, tree, filter)

Build a TreeMimicryPivoting strategy. refpos/pos are the reference positions to mimic (e.g. parent pivots) and the candidate point positions; tree is a tree adapter providing center, values, children and firstchild (the ACAH2Trees extension supplies a ready-made adapter for H2Trees.TwoNTree).

The three-argument form uses the default NoFilter (no directional restriction). Pass an explicit filter (a PivotingFilter, e.g. EFIEDirectionalFilter) to restrict tree descent and pivot selection.

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)
• FullPivoting: Selects the largest residual entry in the complete matrix

ValuePivStratFunctor <: PivStratFunctor

Abstract type for stateful value-based pivoting functors.

_LUEliminationStep

One step of the recursive block LU after the child cluster τ₁ of a cluster τ has been factorized; τ₂ is the part of τ after τ₁:

• pivots: apply the leaf pivots of τ₁ to the blocks left of it within τ, and with update also to A12 = A[τ₁, τ₂];
• upper: solve U12 = L11 \ A12 (a left _SolvePlan);
• lower: solve L21 = A21 / U11 (a right _SolvePlan);
• schur: update A22 -= L21*U12 (a _ProductPlan).

update is false for the last child, which has no trailing block.

_LUPivotPlan(L::HMatrixTriangular, B::HMatrixBlock)

Leaf row permutations of an elimination step, applied to the already factorized blocks B left of its diagonal cluster within the parent cluster (the LAPACK-style row interchanges of L21). A block may extend over several leaves; for a low-rank block the permutation acts on the rows of U.

_MatVecPlan

Output partition of one product direction of a MatVecWorkspace. Chunks are disjoint, contiguous tree-order ranges of balanced cost; entries[ptr[c]:(ptr[c + 1] - 1)] are the CSR entries whose output range overlaps chunk c. Blocks crossing a chunk border are split by output rows, so parallel chunks never write the same entries and need no locking.

_ProductGroup

All contributions to one destination terminal destination of a product, restricted to rows × cols: the terminals of A and B it reads (aentries, bentries), the low-rank panels it multiplies itself (afar, bfar) and its nearest _ProductNode (node, zero if none). The execution strategy is fixed at plan time (implicit) or chosen from the current ranks before each execution (capacity of pending update columns, dense core); denserank is the summed inner dimension of its dense/dense terminal pairs.

_ProductNode

Virtual block (row cluster × column cluster) above at least two complete destinations of a product. It collects the low-rank panels whose terminal strictly contains these destinations, forms their product once, adds the slice of its parent node and is recompressed once. estimate is its current rank bound, used to size the buffers of the destinations below it. See _ProductPlan.

_ProductOperator

Implicit far destination C + α*A*B for _sketchrecompression!, applied through hierarchical thin products (_thinmul!). Its cost is the storage of the operands' panels times the sketch width, however many low-rank terminals contribute. inner holds B*Ω or Q'*A, adjointq holds Q'.

_ProductPanel

A low-rank terminal entry of one operand together with the hierarchical panel of the other operand it multiplies: the terminals entries, clipped to rows × cols. A far terminal U*V of A contributes U * (V*B[panel]), one thin product with the whole panel instead of one product per terminal pair.

_ProductPlan(C::HMatrixBlock, A::HMatrixBlock, B::HMatrixBlock; batchrank=128)

Reusable plan for C += α*A*B on hierarchical blocks whose corresponding axes share cluster trees; the terminal partitions may differ. Ranks may change between executions, the partitions may not. It is the kernel of mul!, of the Schur-complement updates of the LU factorization and of the updates in the triangular solves.

The plan has one _ProductGroup per destination terminal of C, which collects every terminal pair of A and B meeting it:

• dense × dense pairs contribute exact factor slices, or are summed into a dense m × n core once their inner dimensions reach mn/(m+n);
• a low-rank terminal multiplies the whole hierarchical panel of the other operand at once (_ProductPanel);
• a low-rank terminal whose rows (or columns) strictly contain several complete destinations is attached to a virtual _ProductNode above them: its product is formed and recompressed once, and the destinations receive a slice of their nearest node;
• a complete far destination is recompressed directly from the implicit operator C + α*A*B (_ProductOperator) when that is estimated to be cheaper.

Low-rank updates are collected as pending columns, at most batchrank per far destination, and recompressed together with the destination. Buffers belong to the executing task's scratch, so nodes and destinations can run on different tasks; nodes run before the nodes and destinations below them (see _productgraph).

_ProductStatus

Truncation status accumulated over a sequence of recompressions: whether all met the tolerance (converged), whether any was capped by maxrank (rank_limited), the largest discarded spectral error of a block (max_block_error) and the number of recompressions (flushes). Updated with _record!; reported by lu! through HMatrixLU.

_SolvePlan(H::HMatrixTriangular, B::HMatrixBlock; side=:left, batchrank=128)

Reusable plan of the triangular solve H*X = B (side=:left) or X*H = B (side=:right) with a hierarchical right-hand side B, overwritten by X. The LU factorization uses it for the off-diagonal panels U12 = L11 \ A12 and L21 = A21 / U11.

Each step owns one terminal block of B, in the elimination order of the factor: it first subtracts the product of the coefficient block of H with the already solved blocks before it (a _ProductPlan), then solves with the factor of the diagonal cluster of its rows (left) or columns (right). A low-rank block is solved through its left factor U (left) or right factor V (right) alone, so the solve itself does not change its rank. Steps are executed by _executesolveoperation!. Ranks may change between executions, the partition may not.

_TaskGraph

Dependency graph of a sequence of tasks in serial program order, in compressed successor form: the tasks depending on task t are succ[succptr[t]:(succptr[t + 1] - 1)], and indegree[t] counts the tasks t waits for. Built with a _TaskGraphBuilder and executed by _rungraph!.

_TaskGraphBuilder(nresources)

Builds a _TaskGraph from tasks appended in serial program order with _addtask!. Every task names the resources (block entries) it reads and writes. A task depends on the last earlier writer of each resource it touches and on the earlier readers of each resource it writes. Any execution order that respects these edges therefore computes exactly the serial result, bit for bit.

_TreeIndex(H::HMatrixCore)

Read-only tree-order analysis of H, shared by the workspaces built from it. rowperm and colperm map tree positions to external indices (IdentityPermutation for spaces already in tree order), rowranges and colranges map cluster IDs to contiguous tree-order ranges, and entryrows maps CSR entries to their row clusters.

_TreeView(H::HMatrixCore)

Tree-order view of H on which all hierarchical arithmetic operates. Rows and columns are numbered in cluster-tree order, so every cluster is a contiguous range (rowranges, colranges), and entryrows maps each CSR entry to its row cluster. rowperm and colperm map tree positions to the external indices.

The vectors near and far reference the blocks of the bound matrix, so arithmetic through the view overwrites that matrix. Plans address blocks only through these vectors and the CSR storage indices: _bind! moves a view, and with it every plan built on it, to another matrix with the same trees and block partition. Requires full (not symmetric half-) storage.

_Worker{T}()
_Worker(scratch::BlockScratch)

Execution context of one parallel task of a workspace: its BlockScratch and the _ProductStatus of the recompressions it performed. The statuses of all workers are combined by _workerstatus after a run.

_addlowrank!(C::LowRankMatrix, A::LowRankMatrix, α, scratch; atol=0, rtol=1e-6, maxrank)

Replace C by a recompressed approximation of C + α*A, with tolerances relative to the sum. The factors are stacked, [C.U α*A.U] * [C.V; A.V], and truncated by _flushfactors!. Returns the truncation information of _recompressionrank.

_addmul!(P::_ProductPlan, α, workers, graph::_TaskGraph, options)

C += α*A*B with the blocks of the plan, distributed over workers along graph (from _productgraph(P)). Every touched far block is recompressed to options. Returns the aggregated truncation status.

_addtask!(builder::_TaskGraphBuilder, reads, writes, after=())

Append a task that reads the resources reads and writes writes; after lists further tasks it must follow. Returns the index of the new task.

_bind!(W::_TreeView, H::HMatrixCore)

Point the block vectors of W to the blocks of H, which must have the same trees and block partition as the matrix W was built for; ranks may differ. Plans built on W then operate on H without being rebuilt.

_executegroup!(P::_ProductPlan, g::_ProductGroup, α, scratch, status, options)

Apply all updates of destination g. A dense destination is updated directly with BLAS. A far destination is recompressed from the implicit operator if planned so; otherwise its low-rank panel products, the slice of its nearest node and its dense/dense pairs are collected as pending factor columns (beside a dense core if chosen) and recompressed together with the destination, in batches of at most capacity columns. Its nearest node must already have run.

_executenode!(P::_ProductPlan, n, α, scratch, status, options)

Form the low-rank factors of virtual node n: the slice of its parent's result plus the thin products of its own low-rank panels, recompressed once with a sketch. The result is kept in P.results[n] until the destinations below it have run. The parent node must already have run.

_executesolveoperation!(P::_SolvePlan, step, scratch, status, options)

Execute step step of P: subtract the products with the already solved blocks, recompressing a low-rank block to options, and solve with the diagonal subfactor. The truncation information is added to status.

_factorize!(ws::LUWorkspace, options, check, checkfinite)

Recursive block LU of the matrix bound to ws: each elimination step applies the leaf pivots of its diagonal cluster to the panels left and right of it, solves for the off-diagonal panels L21 and U12 and updates A22 -= L21*U12. The block operations run on the workers of ws as soon as their inputs are final. With check=false the factorization stops at the first singular leaf. Returns the aggregated truncation status.

_filterstate(filter::PivotingFilter, convcrit) -> PivotingFilterState

Build the per-factorization PivotingFilterState for filter, given the factorization's convergence criterion convcrit. Direction-phased filters consult convcrit to decide when a phase is finished and therefore store it in their state; such filters provide a method. NoFilter needs no convergence criterion and is built directly, so it does not implement this hook.

_flushfactors!(C::LowRankMatrix, X, Y, scratch; atol, rtol, maxrank, α=1, sketch=false, guess)

Replace C by a recompression of C + α*X*Y in one pass. The deterministic path stacks the factors, [C.U X] * [C.V; Y], and truncates them by QR of the left factor, LQ of the right factor and an SVD of the small core; when the stacked rank reaches both dimensions, the dense sum is truncated instead. With sketch=true, wide updates first try _sketchrecompression!, whose cost is linear in the stacked rank; guess is its first sample count. Returns the truncation information of _recompressionrank.

_hierarchicaladd!(C::_TreeView, A::_TreeView, α, workers, options)

C += α*A for views with identical trees and partitions; their storage orders may differ. Dense blocks are updated exactly and every far block is recompressed once (see _addlowrank!). The blocks are independent and distributed over workers. C += α*C is an exact scaling. Returns the aggregated truncation status.

_implicitcheaper(C, A, B, k, rows, cols, ai, bi, denserank, parents)

Plan-time flop model for the complete far destination k, with the ranks at planning time. Implicit: every sketch column passes once through B(inner, cols) and A(rows, inner). Factors: each local low-rank term (ancestor terms are shared through nodes) costs a thin product plus its pending columns in the sketch, and dense pairs enter as factor slices or a dense core. Returns whether the implicit operator is cheaper.

_lugraph(W, lower, steps, instructions)

Tasks and dependency graph of the factorization. Every leaf LU, pivot application, solve step, Schur node and Schur destination of the serial instruction stream becomes one task; its reads and writes are the physical blocks of W. Schur nodes additionally follow their parent node and destinations their nearest node. See _TaskGraphBuilder.

_lusolve!(F::HMatrixLU, B::StridedMatrix, scratch, transposed)

Solve A*X = B or, with transposed, transpose(A)*X = B in place for B in external order. B is permuted to tree order, where A = P'*L*U and transpose(A) = transpose(U)*transpose(L)*P, solved with the dense triangular solves _trisolve!, and permuted back.

_luworkspace(W::_TreeView; batchrank=128, ntasks=Threads.nthreads())

Plan the LU factorization of the matrix bound to W. The cluster tree is traversed in depth-first order: every leaf is factorized when reached, and after each child cluster except the last an _LUEliminationStep eliminates it from the trailing block of its parent. The resulting serial instruction stream is turned into a task graph by _lugraph.

_nchunks(ntasks)

Number of cost-balanced chunks of a loop over many cheap items on ntasks tasks: eight per task, so that the greedy scheduler can balance the remaining cost differences, and one for a single task.

_productgroups(C, A, B)

Analyse the terminals of a product: the _ProductGroup of every destination of C, the candidate virtual nodes kept where they serve at least two complete destinations (ordered parents first), and the assignment of every low-rank terminal to its node or to the panels of its destination. Returns (groups, nodes).

_recompress!(R::LowRankMatrix, scratch; atol=0, rtol=1e-6, maxrank=typemax(Int))

Replace the factors of R = U*V by a truncated reduced SVD: QR of U, LQ of V, SVD of the product of the two triangles. The new rank is the smallest one whose largest discarded singular value is at most max(atol, rtol*opnorm(R)), capped at maxrank. The new factors own their storage. Returns the truncation information of _recompressionrank.

_recompressionrank(s, atol, rtol, maxrank; residual=0)

Truncation rank for the singular values s: the smallest k with s[k + 1] + residual <= max(atol, rtol*s[1]), capped at maxrank. residual bounds an error committed before this SVD, such as the range-finder error of _sketchrecompression!; it is charged against the tolerance.

Returns (; rank, error, tolerance, converged, rank_limited), where error is the spectral error of the truncated block and rank_limited marks a cap by maxrank. Every recompression of the arithmetic returns this information.

_rungraph!(f, G::_TaskGraph, workers)

Run every task of G with one parallel task per element of workers. f(t, worker) executes task t with the scratch and status of worker and returns false to stop starting new tasks.

A single worker runs the tasks in program order on the calling task. Several workers share a min-heap of ready tasks and always take the earliest one in program order, so the execution stays as close to the serial order as the dependencies allow. The first exception is rethrown after all workers have returned.

Returns false if the run was stopped by f, otherwise true.

_scheduler(ntasks)

Scheduler of the parallel loops over independent items (assembly, matrix-vector products, recompression) on ntasks tasks: a GreedyScheduler, where each task takes the next item as soon as it is done, which balances items of uneven cost. ntasks = 1 runs serially on the calling task. The public functions only take ntasks; operations with dependencies use a task graph instead.

_sketchrecompression!(S, m, n, guess, qcap, scratch, atol, rtol, maxrank)

Randomized spectral-norm recompression of an implicit m × n operator S (adaptive randomized range finder of Halko, Martinsson & Tropp 2011, Alg. 4.2, with blocked sampling). S only needs to apply itself to a block of vectors (_sketchapply!) and to project onto a basis (_sketchproject!), so sums of factors and hierarchical products are never formed explicitly.

The first guess samples build an orthonormal basis Q. Each further block of p = 8 Gaussian samples, projected onto the complement of Q, certifies

‖(I - QQ')S‖ ≤ 10 √(2/π) maxᵢ ‖(I - QQ')S ωᵢ‖

except with probability 10^-p, or is appended to Q. The bound is driven below a tenth of the tolerance and charged against it after the SVD of Q'S (see _recompressionrank). The sampling RNG has a fixed seed, so results are reproducible.

Returns (U, V, info), or nothing if Q would exceed qcap columns; the caller then falls back to a deterministic QR/LQ/SVD recompression.

_thinmul!(Y, H::HMatrixBlock, X, α, β, scratch, Val(side))

Product of a hierarchical block with a dense panel: Y = α*H*X + β*Y (side=:left) or Y = α*X*H + β*Y (side=:right), in tree order. Every terminal block applies the whole panel at once, a low-rank block as U*(V*X); the cost is the storage of H times the panel width. This is the kernel behind the products of low-rank terminals with hierarchical panels and the triangular solves.

_trisolve!(B::StridedMatrix, H::HMatrixTriangular, scratch, Val(op), Val(side))

Solve op(H)*X = B (side=:left) or X*op(H) = B (side=:right) in place for a dense right-hand side in tree order, with op :N or :T. The solve recurses over the cluster tree: leaves use BLAS trsm, and after each child cluster its panels update the remaining part of B with thin products. The pivots are not applied.

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))

The convergence criterion targets the requested tolerance. The achieved matrix error also depends on the pivot sequence, convergence estimator, and maxrank.

SVD Recompression

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

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

Compute column-first 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))

The convergence criterion targets the requested tolerance. The achieved matrix error also depends on the pivot sequence, convergence estimator, and maxrank.

SVD Recompression

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

assemble(op, testspace, trialspace; tree=..., quadstrat=..., kwargs...)

Assemble a hierarchical matrix with automatic tree-based blocking.

High-level convenience function that automatically constructs a hierarchical clustering tree and assembles the complete HMatrix with near and far-field blocks. This is the recommended entry point for most applications.

Arguments

• op: Operator/kernel for matrix entry evaluation

• testspace: Test space (row basis/points)

• trialspace: Trial space (column basis/points)

• tree: Hierarchical tree structure. Auto-generated from AdaptiveCrossApproximation.defaulttreebackend() if not provided: a H2Trees.TwoNTree when only H2Trees.jl is loaded, or a k-means clustered tree when ParallelKMeans.jl is loaded alongside it.

• treekwargs: Keyword arguments forwarded to the automatic tree construction (e.g. minvalues, numberofclusters for the k-means backend); ignored if tree is given explicitly.

• quadstrat: Quadrature strategy, matching BEAST.assemble's keyword of the same name. Defaults like BEAST.defaultquadstrat(op, testspace, trialspace) for BEAST operators (via the ACABEAST extension).

• nearquadstrat: Quadrature strategy for near-field (dense) blocks. Defaults to quadstrat.

• farquadstrat: Quadrature strategy for far-field (compressed, admissible) blocks. Defaults to tofarquadstrat(quadstrat), which strips singular-quadrature handling since far blocks are always well-separated.

• kwargs...: Additional parameters passed to HMatrix:

  • tol: Convergence tolerance (default 1e-4); also governs every later recompression of the hierarchical arithmetic
  • maxrank: Maximum rank for compression (default 40)
  • compressor: ACA-style compressor. The default is selected by defaultcompressor(op, testspace, trialspace; tol) and is usually ACA.
  • isnear: Admissibility predicate (default isnear())
  • spaceordering: Space ordering strategy (default PreserveSpaceOrder())
  • ntasks: Number of parallel assembly tasks (default Threads.nthreads())
  • verbose: Enable progress output (default true)

Returns

• HMatrix: Assembled hierarchical matrix

Notes

Requires H2Trees.jl to be loaded for automatic tree generation. If providing a custom tree, ensure it implements the tree interface expected by HMatrix assembly. The two-space call uses general assembly even when testspace === trialspace. For a transpose-symmetric operator, use assemble(op, space; kwargs...) to select symmetric assembly explicitly. For operators whose matrix is cheap to build directly and never benefits from low-rank compression (e.g. BEAST's local operators Identity/NCross), the ACABEAST extension adds a more specific assemble method that bypasses tree construction and ACA entirely, calling BEAST.assemble directly.

Examples

# With BEAST boundary integral operators
hmat = AdaptiveCrossApproximation.assemble(op, testspace, trialspace; tol=1e-5, maxrank=100)
y = hmat * x  # Efficient matrix-vector product

See also

HMatrix

assemble(op, space; tree=..., quadstrat=..., kwargs...)

Assemble a transpose-symmetric H-matrix on one space. Automatic tree construction builds one shared cluster tree. With an explicit tree, only its test cluster tree is used for both axes.

The operator and any custom isnear predicate must be transpose-symmetric; this is a caller-supplied assumption and is not checked. Opposite off-diagonal blocks use a transpose, without complex conjugation. Diagonal near blocks are assembled in full and symmetrized. Each unordered far-field pair is compressed once with the configured compressor.

Accepts the tree, quadrature, compression, ordering, and ntasks keywords of the two-space overload. The call assemble(op, space, space) uses general assembly. BEAST local operators such as Identity and NCross are assembled directly.

Examples

hmat = AdaptiveCrossApproximation.assemble(op, space; tol=1e-5)
hmat = AdaptiveCrossApproximation.assemble(op, space; tree=tree, tol=1e-5)

See also

HMatrix

assemble_blocks(matrix::AbstractKernelMatrix, blocks, rowidcs, colidcs; ntasks, pbar) -> blocks

Fill each preallocated blocks[i] (sized (length(rowidcs[i]), length(colidcs[i]))) with the requested kernel entries. The built-in kernel backends accumulate into the supplied blocks, so callers should normally provide zero-initialized storage.

rowidcs/colidcs need not describe disjoint or contiguous index ranges — they can be the cluster indices of near-field blocks (see interactions) but also scattered pivot-index blocks (e.g. the far-field coupling blocks of a nested cross approximation), since both are just lists of (row-index-list, column-index-list) requests against the same underlying kernel.

Taking blocks as an argument (rather than allocating and returning it) lets callers own the storage layout (e.g. the near blocks of an HMatrix) and lets backends override just the fill strategy — e.g. a GPU backend can force a serial loop, or batch everything through one combined pass — without duplicating the surrounding preallocation/storage-construction code.

Default (any AbstractKernelMatrix) implementation: a plain per-block loop on ntasks parallel tasks (default Threads.nthreads()).

assemblefars(operator, testspace, trialspace, tree, partition; compressor, maxrank,
    matrixdata, ntasks, verbose=true)

Compress the far-field blocks of the terminal blocks partition (see interactions). The test clusters are processed in parallel on ntasks tasks; each task owns one compressor and one pair of factor buffers, sized for the largest far-field block, and reuses them for all its blocks.

Returns

A Vector{LowRankMatrix{T}} in the order of partition.farnodes.

assemblenears(operator, space, tree, partition; matrixdata, ntasks, verbose=true)

Assemble the near-field blocks of the transpose-symmetric terminal blocks partition (see symmetricinteractions) on one space. Self blocks are assembled in full and then made symmetric by copying their upper triangles into their lower triangles.

assemblenears(operator, testspace, trialspace, tree, partition; matrixdata, ntasks,
    verbose=true)

Assemble the dense near-field blocks of the terminal blocks partition (see interactions) through assemble_blocks on ntasks tasks.

Returns

A Vector{Matrix{T}} in the order of partition.nearnodes.

basisfunction_orientation_ids(edges, normals; edge_digits=1, normal_digits=1)

Assign integer orientation-group ids to a set of basis functions from their edge directions and face normals.

Arguments

• edges: one direction vector per basis function (e.g. RWG edge directions)
• normals: one normal vector per basis function; zero vectors are treated as "no normal" and get id 0

Returns

• (edgeids, normalids, nedgeids, nnormalids): per-basis-function group ids for edges and normals (both Vector{Int32}), plus the number of distinct groups found for each. Directions that are antiparallel (up to rounding at digits decimal places) are assigned the same id, since only the underlying line matters for orientation grouping.

See also

node_normal_orientation_sets, orientation_ids, normal_orientation_ids

beastkernelmatrix(operator, testspace, trialspace, matrixdata)

Build a BEAST-backed kernel matrix (e.g. BEASTKernelMatrix) from a BEAST operator, spaces, and matrixdata (a quadrature strategy).

No default method is provided here; it is implemented by the ACABEAST package extension and dispatched to from AbstractKernelMatrix(operator, testspace, trialspace; matrixdata=...) when BEAST types are detected.

blockindices(tree, partition)

Block index (csr, csc) of the terminal blocks partition of interactions: the k-th near block refers to near[k], the k-th far block to far[k].

blockview(W::_TreeView)
blockview(W::_TreeView, rows::UnitRange, cols::UnitRange)
blockview(W::_TreeView, rownode::Int, colnode::Int)

Hierarchical block of W over tree-order rows × cols, or over the ranges of a row and a column cluster. The terminal entries are collected by descending the cluster tree of the axis of which the block covers the smaller fraction. The full view needs no entry vector.

defaultcompressor(operator, testspace, trialspace; tol=1e-4)

Return the compressor used by HMatrix and AdaptiveCrossApproximation.assemble when none is supplied explicitly. The fallback is ACA(; tol). Extensions may select a more robust compressor for particular operator and space combinations.

defaultmatrixdata(operator, testspace, trialspace)

Return backend-specific data used to construct an AbstractKernelMatrix during hierarchical assembly. The fallback returns nothing; extensions may return quadrature rules or other reusable assembly data.

defaulttreebackend()

Return the tree backend assemble uses when no tree is given explicitly.

Resolved at call time from which packages are loaded: KMeansTreeBackend if ParallelKMeans.jl is loaded alongside H2Trees.jl (via the ACAParallelKMeansTrees extension), otherwise H2Tree if H2Trees.jl alone is loaded (via ACAH2Trees). Errors if neither is loaded, since assemble then has no way to build a tree.

farmatrix(H::HMatrixCore)

Far-field part of H: the low-rank blocks only, as a lazy linear map sharing the blocks of H (see HMatrixComponent). Useful to analyse the rank structure or to apply it separately.

interactions(tree; isnear=isnear())
interactions(tree, isnear)

Terminal blocks of the block tree tree: the admissible (far-field) cluster pairs and the near-field pairs of which at least one cluster is a leaf. Tree backends implement the positional method.

Return a named tuple (; nearptr, nearnodes, farptr, farnodes) in compressed row storage over all nodes of testtree(tree): the near blocks of test node τ are the trial nodes nearnodes[nearptr[τ]:(nearptr[τ + 1] - 1)], its far blocks farnodes[farptr[τ]:(farptr[τ + 1] - 1)]. The position of a block in nearnodes or farnodes is its position in the near or far storage of an HMatrix. The index sets of a node are given by values(tree, node). Use symmetricinteractions to visit each unordered pair once.

isnear(η::Real=1.0; crosslevel=false)

Create a geometric admissibility functor for near-field block detection. The functor returns true for cluster pairs requiring dense assembly or subdivision, and false for admissible far-field pairs. For the H2Trees backend, larger η classifies more cluster pairs as far field. Custom callables can instead be passed directly as the isnear argument of assembly and interaction traversal functions.

Cross-level traversal is reserved for future implementation and currently requires crosslevel=false.

DenseLeafLU <: LinearAlgebra.Factorization
leaflu!(A; node=0, check=true, checkfinite=true)
leaflu!(F::DenseLeafLU; check=true, checkfinite=true)

Pivoted LU P*A = L*U (unit-diagonal L) of a square dense diagonal leaf, in place: F.factors === A. The second form factorizes new values written into F.factors, reusing the pivot storage. ipiv holds LAPACK's sequence of local row swaps. info == 0 means success, a positive info a zero pivot, which throws a LeafLUFailure unless check=false; info == -1 marks an invalid state. checkfinite=false skips the scan for nonfinite input.

localkernelmatrix(matrix::AbstractKernelMatrix, rows, columns)

Prepare a matrix-like object for repeated row and column sampling of one block.

The fallback returns matrix unchanged. A backend may return a lightweight local wrapper that precomputes block-dependent assembly data. The returned object must accept the original global indices through the same nextrc! interface and report the same global size and eltype as matrix.

Rows are sampled against exactly columns and columns against exactly rows, in the given order. If only one kind is sampled, the other index set may be nothing: localkernelmatrix(matrix, rows, nothing) prepares only column sampling and localkernelmatrix(matrix, nothing, columns) only row sampling, which avoids preparing data for a side that is never used as an index list.

This hook is called once per far-field block before ACA compression, so any cached state belongs to that block and must not be shared concurrently between blocks.

nearmatrix(H::HMatrixCore)

Near-field part of H: the dense blocks only, as a lazy linear map sharing the blocks of H (see HMatrixComponent). Useful to analyse the near-field structure or to apply it separately.

nextrc!(buf, A, i, j)

Fill buf in place with the entries A[i, j] (a sampled row/column block).

Either index may be an integer for a single row or column, or an index collection for a larger block. buf must retain the corresponding two-dimensional shape; for example, a single row is written into a 1 × length(j) buffer.

Interface method used by ACA, ACAᵀ and IACA to pull the row/column samples they pivot on, so A need not materialize as a dense matrix. The fallback here covers any AbstractArray; kernel-matrix backends (AbstractKernelMatrix subtypes such as BEASTKernelMatrix or PointMatrix) provide their own methods that evaluate entries on demand.

nnz(H::HMatrixCore)

Number of stored scalars of H: the entries of the dense blocks plus length(U) + length(V) for every low-rank block. Blocks shared by both orientations of a symmetric matrix count once. Index arrays and object overhead are not included. See also storage.

node_normal_orientation_sets(normals, tree; normal_digits=1, max_orientations=3,
    primary_probability=0.2, secondary_probability=0.1, active_probability=0.7,
    orth_tol=0.25)

Determine, per tree node, which basis-function normal directions dominate its subtree.

Walks tree top-down (a node must implement values, children, parent; see TreeMimicryPivoting). At each node it counts how often each normal-direction group occurs among its basis functions and selects up to max_orientations mutually (near-)orthogonal directions (via orth_tol on abs(dot(·,·))) that together explain at least active_probability of the node's basis functions, requiring the dominant direction to cover at least primary_probability and secondary ones at least secondary_probability. If no direction set is dominant enough, the node inherits its parent's set. Used to drive the EFIEDirectionalFilter, which restricts descent/pivoting to one orientation group at a time.

Returns

• (nodesets, normalids, nnormalids): nodesets[node]::Vector{Int32} is the set of dominant direction ids for node; normalids/nnormalids are as returned by normal_orientation_ids on normals.

See also

basisfunction_orientation_ids, EFIEDirectionalFilter

normal_orientation_ids(q)

Like orientation_ids, but zero-valued keys (i.e. "no normal") are left at id 0 instead of starting a new group.

Returns

• (ids, nids): per-entry group ids (0 for zero keys) and the number of distinct non-zero groups found.

orientation_ids(q)

Assign a sequential Int32 id to each distinct value in q, in order of first occurrence. Every entry gets an id (starting at 1); use normal_orientation_ids instead if zero-valued keys should be exempt (id 0).

Returns

• (ids, nids): per-entry group ids and the number of distinct groups found.

recompress!(H::HMatrixCore[, workspace::RecompressionWorkspace])

Recompress every low-rank block of H in place to the smallest rank meeting H.tol in the spectral norm (relative to the block). Assembly by ACA does not produce optimal ranks, so this usually reduces storage and the cost of later products and factorizations. The partition does not change.

reset!(convcrit::ConvCritFunctor)

Reset a convergence functor before starting compression of a new block.

Notes

Concrete subtypes should overload this method. The default fallback throws ArgumentError.

See also

ConvCritFunctor

reset_phase!(convcrit::PhaseExtrapolatorFunctor, direction::Integer)

Set the current phase label. Call before each new pivot to associate it with a direction.

rwgorientations(space)

Compute per-basis-function edge directions and face normals for space.

Returns (edges, normals), one unit vector each per basis function, suitable as input to basisfunction_orientation_ids and node_normal_orientation_sets.

Implemented in the ACABEAST extension for BEAST Raviart–Thomas spaces.

scalartype(operator)

Return the scalar element type produced by evaluating operator.

Interface point for custom operators used with AbstractKernelMatrix backends; e.g. the ACABEAST extension implements this for BEAST integral operators. No default is provided — implement a method for your operator type.

storage(H::HMatrixCore)

Report the storage of H. Prints the numerical block payload (nnz scalars) in GB, the complete Julia object footprint reported by Base.summarysize in GB, and the ratio of the payload to dense storage.

Returns

• Float64: numerical block payload in GB

symmetricblockindices(tree, partition)

Block index (csr, csc) of the transpose-symmetric terminal blocks partition of symmetricinteractions: every stored pair (a, b) and, for a != b, the opposite block (b, a) as the transpose of the same stored block.

symmetricinteractions(tree; isnear=isnear())
symmetricinteractions(tree, isnear)

Terminal blocks of a transpose-symmetric block tree, each unordered pair once. Only the test cluster tree is used for both axes; the admissibility predicate must be transpose-symmetric.

Return the format of interactions, restricted to pairs (a, b) with a <= b. The opposite block of a < b is the transpose of (a, b).

testtree(tree)
trialtree(tree)
BlockTree(testtree, trialtree)
root(tree)
children(tree, node)
parent(tree, node)
firstchild(tree, node)
isleaf(tree, node)
leaves(tree)
center(tree, node)
values(tree, node)
numberofnodes(tree)
numberofvalues(tree, node)
levels(tree)
LevelIterator(tree, level)

Tree backend interface required by HMatrix assembly and TreeMimicryPivoting. Names and semantics match H2Trees; the ACAH2Trees extension forwards these methods to that backend. testtree/trialtree return the row/column cluster trees, and BlockTree combines them. values(tree, node) returns the indices in a node's subtree in traversal order; at the root these give the tree-to-space permutation. levels lists levels coarsest first, visited via LevelIterator.

tofarquadstrat(quadstrat)

Convert a near-field quadrature strategy into the strategy used for admissible (far-field, well-separated) blocks.

Falls back to returning quadstrat unchanged. The ACABEAST extension specializes this for BEAST.DoubleNumWiltonSauterQStrat to extract its non-singular outer_rule_far/inner_rule_far orders into a plain BEAST.DoubleNumQStrat, since far blocks are by construction well-separated and never need singular quadrature.

update_refcentroid!(functor::PivStratFunctor, refidcs)

Update the stored reference-domain centroid in pivoting functors that track it. The default implementation is a no-op; concrete subtypes override as needed.

A * B

Product of two H-matrices as a new HMatrixCore with the block partition of A and the larger tolerance of the two.

A + B
A - B

Sum of two H-matrices with the same cluster trees and block partition, as a new HMatrixCore with the larger tolerance of the two.

H \ B

Solve H*X = B with a hierarchical LU factorization of a copy of H; H is unchanged. Each call factorizes again: for several solves with the same matrix, keep F = lu(H) and solve with F \ B.

copy(H::HMatrixCore)

Copy the numerical blocks of H. Tree and block index are shared, so the copy has the same partition and can reuse workspaces built for H.

axpy!(α, A::HMatrixCore, C::HMatrixCore[, workspace::AdditionWorkspace])
axpby!(α, A::HMatrixCore, β, C::HMatrixCore[, workspace])

Overwrite C with α*A + C (or α*A + β*C). Both matrices need the same cluster trees and block partition. Dense blocks are added exactly; every low-rank block is recompressed once to the larger tolerance of A and C. A is not modified; A === C is allowed.

lu!(H::HMatrixCore[, workspace::LUWorkspace]; check=true)

Hierarchical LU factorization of H in place: the blocks of H are overwritten by the factors, so H no longer represents the original matrix. Every block update is recompressed to H.tol. A LUWorkspace from an earlier factorization of a matrix with the same partition avoids planning again. With check=false, a singular dense diagonal leaf returns a factorization with issuccess(F) == false instead of throwing a LeafLUFailure. Requires full (not symmetric half-) storage.

lu(H::HMatrixCore[, workspace::LUWorkspace]; check=true)

Hierarchical LU factorization of a copy of H; H is unchanged. See lu!.

mul!(C::HMatrixCore, A::HMatrixCore, B::HMatrixCore, α=true, β=false[, workspace])

Overwrite C with α*A*B + β*C, recompressed to the largest tolerance of the three matrices. A and B are not modified and must not be C. The row cluster tree of C is that of A, its column tree that of B, and the column tree of A the row tree of B; the block partitions may differ.

rmul!(H::HMatrixCore, α)
lmul!(α, H::HMatrixCore)

Scale H in place by α. Exact; dense blocks are scaled and every low-rank block scales its smaller factor. α = 0 leaves rank-zero low-rank blocks.