Sparse matrix preprocessing

1 Problem setup and motivation

1.1 What “preprocessing” means for sparse matrices

Sparse matrix preprocessing is the collection of transformations applied to a sparse matrix (and often accompanying vectors or constraint objects) before it enters a downstream computation such as a direct factorization, an iterative linear solver, graph-derived routines, or parts of a machine learning pipeline. The emphasis is on reshaping the data and metadata so that later algorithms encounter a form that is faster to process, more stable numerically, and better aligned with their structural requirements.

Preprocessing is not a single operation; it is usually a staged workflow. Typical stages include cleaning the raw sparsity pattern, standardizing indices, reordering for performance, scaling to improve conditioning, converting to the storage format expected by kernels, and preparing solver- or preconditioner-specific auxiliary structures.

1.2 Typical downstream workloads and why they need preprocessing

Downstream sparse workloads often impose assumptions about ordering, storage layout, sparsity pattern, or diagonal structure. For example, many factorization routines benefit substantially from reducing fill-in, which depends on the elimination order. Iterative methods can converge more quickly when the spectrum is better behaved, which motivates scaling or regularization. Graph-based computations interpret the sparsity pattern as an adjacency structure and therefore depend on consistent, duplicate-free edge lists.

In machine learning contexts, sparse preprocessing may aim to align with mini-batching, reduce memory footprint for embedding operations, or create normalized matrices for graph convolution–style steps. In all these settings, preprocessing helps ensure that expensive later kernels spend time on arithmetic rather than on handling irregular or inconsistent data.

1.3 Metrics: speed, memory, fill-in, and stability

Common evaluation criteria for preprocessing include:

Runtime: end-to-end time spent in the preprocessing stage plus the time saved downstream.
Memory use: peak storage for sparse representations, intermediate fill-in during factorization, and temporary buffers during conversions.
Fill-in: additional nonzeros created by elimination or incomplete factorization, often controlled by reordering and pattern restrictions.
Numerical stability: sensitivity to scaling, the behavior of pivoting or breakdown conditions, and the reduction of ill-conditioning that can slow iterations or degrade direct solves.
Accuracy-related diagnostics: residual norms, consistency checks, and sensitivity to floating-point effects.

Because preprocessing can change both structure and values, it is evaluated through a combination of structural metrics (e.g., nonzero counts, symmetry preservation) and numerical metrics (e.g., convergence rate or residual quality).

2 Sparsity structure characterization

2.1 Matrix storage formats and layout concerns

Sparse preprocessing begins with understanding how the matrix is stored, since layout affects both speed and correctness. Many algorithms expect a specific format and may assume ordering or uniqueness of indices. In addition, certain operations—such as merging duplicates or pruning small entries—are easiest in some formats and more expensive in others.

2.1.1 Coordinate (COO) representation

COO stores entries as triplets (row, column, value). It is flexible for ingesting data and for intermediate steps where entries may be appended or modified. However, COO typically lacks fast random access and may contain duplicate coordinates that must be resolved. Preprocessing in COO often focuses on canonicalization, duplicate removal, and conversion to compressed formats.

2.1.2 Compressed Row (CSR) and Compressed Column (CSC)

CSR stores, for each row, a contiguous list of column indices and corresponding values. CSC is the column-wise analogue. These formats enable efficient row or column traversal and are widely used for sparse matrix-vector products and for many factorization pipelines.

Preprocessing that changes row-based structure—such as row permutations, row scaling, or row-wise pruning—is often efficient in CSR. Conversely, operations oriented around columns may be more natural in CSC. Conversions between CSR and CSC are therefore frequently part of interoperability workflows.

2.2 Estimating nonzeros, patterns, and distributions

Beyond counting nonzeros, preprocessing often estimates properties of the sparsity pattern that correlate with performance. Examples include the distribution of nonzeros per row or per column, the presence of very dense rows, and the variability of row lengths. Such statistics help identify load imbalance in parallel runs, potential hotspots in kernels, and whether certain optimizations (like block exploitation) are plausible.

Patterns can also reveal opportunities: if the matrix is nearly banded or has repeated structural motifs, specialized transformations may yield better locality and lower fill-in.

2.3 Symmetry, block structure, and structured sparsity

Many algorithms treat symmetric or Hermitian matrices differently. Preprocessing therefore checks whether the sparsity and values are consistent with a symmetry assumption, not just whether the matrix “looks symmetric” by index count. For structured sparsity, block structures (e.g., repeated 2×2 or 4×4 patterns) can enable block sparse formats that reduce indexing overhead and improve cache behavior.

Structured sparsity can be explicit (known from the modeling problem) or discovered by analyzing index patterns. When such structure is present, preprocessing may reorganize storage or identify blocks for downstream kernels.

2.4 Detecting anomalies: duplicates, zeros, and inconsistent indices

Raw sparse data commonly contains issues that can break correctness or degrade performance:

Duplicate entries: the same (row, column) appears multiple times, requiring merging.
Explicit zeros: entries with value exactly zero may remain and inflate storage.
Out-of-bounds indices: row or column indices beyond declared dimensions.
Inconsistent indices: differing index bases (0-based vs 1-based) or mismatched conventions between matrix and companion vectors.
NaNs or infinities: values that propagate instability or break numerical routines.

Preprocessing identifies these anomalies early so later stages can assume consistent invariants and operate efficiently.

3 Data cleaning and canonicalization

3.1 Merging duplicate entries

When duplicates exist in coordinate input or after certain transformations, they must be combined into a single value per coordinate. Merging is typically performed by sorting coordinates or using hash-based accumulation. The merged value is usually the arithmetic sum, though some pipelines may choose alternative semantics if duplicates arise from special constructions.

Canonicalization ensures that downstream operations—especially factorization and preconditioner setup—do not interpret duplicates as distinct edges, which would distort degrees, fill-in estimates, and numerical results.

3.2 Removing explicit zeros

Explicit zeros increase the number of stored entries without adding information. Preprocessing removes them by thresholding based on exact equality or a tolerance policy. While removing entries with very small magnitude can improve performance and conditioning, the decision is usually conservative when numerical error bounds are a concern.

If the matrix is intended for reproducibility, the policy for zero removal is documented since floating-point pipelines may produce slightly different tiny values across platforms.

3.3 Index normalization and bounds checking

Index normalization addresses differences in index base and validates dimensions. For example, if input is 1-based but the target library expects 0-based indexing, all indices are shifted accordingly. Bounds checks confirm that every row and column index is within valid ranges.

Preprocessing may also enforce consistent ordering within each row (for CSR) or column (for CSC), because some kernels assume indices are sorted for efficient binary search, merge-like operations, or symbolic phase routines.

3.4 Scaling consistency for associated vectors and operators

If preprocessing includes scaling transformations of the matrix (such as diagonal scaling), it often must also transform associated right-hand side vectors, constraint matrices, or operator blocks to preserve the mathematical relationship of the problem. Consistency is especially important when scaling is applied in a way that implicitly changes the variable definitions.

At an implementation level, preprocessing tracks which objects correspond to which variables so that scaling and permutations are applied coherently, avoiding silent mismatches between matrix rows/columns and vector entries.

4 Reordering and permutation strategies

4.1 Why reordering helps: locality and fill-in reduction

Reordering changes the labels of rows and columns (equivalently, the variable ordering). The primary motivation for many solvers is to reduce fill-in during elimination or factorization. Less fill-in means fewer nonzeros in intermediate factors and less memory consumption.

Reordering also affects memory locality: when nonzeros belonging to “nearby” variables become clustered, traversal during sparse matrix-vector products and triangular solves can show better cache utilization. Additionally, parallel implementations can benefit when row lengths and dependency patterns become more balanced.

4.2 Graph model of a sparse matrix

A common conceptual framework treats a sparse matrix as a graph: vertices correspond to variables (rows/columns), and edges correspond to structural nonzero couplings. Many ordering algorithms operate on this graph, aiming to minimize the cost of elimination as captured by graph properties.

4.2.1 Vertex ordering intuition

In elimination, removing a vertex creates fill-in among its neighbors. Therefore, the elimination order governs how many new edges appear. Orders that eliminate “low-degree” vertices early tend to limit fill-in, while more global strategies seek to isolate dense regions and remove them in a controlled sequence.

4.2.2 Edge/adjacency extraction from sparsity

Extracting the adjacency list requires interpreting the sparsity pattern as a set of neighbor relations. Preprocessing may symmetrize the pattern (for undirected assumptions) even if the original matrix is not symmetric, depending on the ordering algorithm’s requirements. Duplicates and self-loops may need to be handled carefully so degrees and adjacency sizes reflect intended structure.

4.3 Common ordering algorithms

4.3.1 Minimum degree and approximate minimum degree

Minimum degree approaches select at each step a vertex with the smallest current degree, aiming to reduce the number of fill edges generated by eliminating it. Exact minimum degree is expensive to maintain; approximate variants track a heuristic degree estimate and update cheaply.

These methods often perform well when the sparsity pattern has a structure that correlates with elimination cost, but they may be sensitive to preprocessing choices such as duplicate handling and pattern symmetrization.

4.3.2 Nested dissection

Nested dissection recursively partitions the graph by separators. The method eliminates vertices in subdomains and postpones separator elimination to reduce fill-in growth. While it can yield strong theoretical and practical fill-in reductions for many grid-like or planar problems, its performance depends on partition quality and the overhead of building partitions.

4.3.3 Reverse Cuthill–McKee and variants

Reverse Cuthill–McKee (RCM) constructs a breadth-first traversal ordering from graph degrees, then reverses the result. RCM is often used for bandwidth reduction and can improve locality in sparse computations. Although its primary goal is not always fill-in minimization, it can still provide good practical performance for certain matrices, especially those with spatial or grid-derived structure.

4.4 Applying permutations and tracking mapping

After selecting an ordering, preprocessing applies it to the matrix by permuting rows and columns consistently (for similarity-like permutations) or according to solver needs. It also records the mapping so that solutions to permuted systems can be transformed back to the original variable order.

Correctness hinges on consistent bookkeeping: a mismatch between row permutation and column permutation can change the meaning of the system if the solver expects a particular transformed form. Preprocessing therefore maintains clear metadata about the permutation vectors and whether they are used as PAP^T, PAQ, or another convention.

4.5 Reordering-aware handling of constraints and blocks

When constraints or block structures exist, reorderings must respect their coupling. For instance, if the system includes fixed reference variables, elimination may need to occur in a way that preserves the constraint set’s structure. Likewise, block sparse formats may require preserving block boundaries to keep the representation efficient.

Preprocessing can include strategies that reorder within blocks while keeping blocks aligned, or reorder blocks as units rather than individual variables, depending on how the target solver exploits block structure.

5 Numerical scaling and equilibration

5.1 Row/column scaling objectives

Scaling transforms the matrix entries to reduce the disparity between magnitudes of rows and columns. The objectives include improving conditioning, reducing the chance of numerical breakdown, and making iterative convergence more predictable.

Scaling is typically performed with diagonal matrices (row scaling, column scaling, or both). When applied correctly, it does not change the solution in the appropriate transformed variable space; however, it changes intermediate numerical behavior and sometimes the conditioning of preconditioners.

5.2 Diagonal scaling methods

Common diagonal scaling strategies attempt to balance norms of rows and/or columns. Examples include scaling based on the inverse of row or column norms, or iterative equilibration methods that repeatedly adjust scaling factors.

The chosen method considers computational cost and robustness. Some techniques require only local information per row/column, while others perform more global iterations to reach a balanced state.

5.3 Norm-based equilibration

Equilibration often uses norms such as the 1-norm or infinity norm to estimate typical magnitudes. For a given row, scaling can be designed so that the row’s norm becomes approximately uniform across rows. For matrices with heterogeneous coefficients, this uniformity can reduce the impact of outlier rows with unusually large or small entries.

Norm-based approaches are popular because they are simple, scalable, and can be implemented directly from sparse traversal of rows or columns.

5.4 Impact on iterative convergence and factorization stability

Scaling can improve iterative methods by reducing extreme eigenvalue disparities associated with badly scaled matrices. It can also reduce numerical issues during factorization by mitigating the effects of very large or very small pivots.

However, scaling can also influence preconditioner structure and may interact with sparsity dropping thresholds or incomplete factorization parameters. As a result, scaling is evaluated in combination with the subsequent solver pipeline rather than treated as an isolated step.

5.5 Scaling in the presence of symmetric or SPD assumptions

For symmetric or symmetric positive definite problems, scaling is often applied in a way that preserves symmetry or positive definiteness, typically via congruence-like transformations. Preprocessing must follow the mathematical structure the downstream method expects; otherwise, a symmetric solver may receive a nonsymmetric or indefinite matrix.

When symmetry is assumed by the algorithm, scaling choices are therefore constrained to preserve structural properties while still improving magnitude balance.

6 Sparsity-preserving transformations

6.1 Pattern tightening and pruning thresholds

Many workflows include pruning entries that are below a chosen magnitude threshold. This aims to reduce storage and computation while maintaining an acceptable approximation to the original operator. “Sparsity-preserving” in this context means the preprocessing primarily constrains or refines the existing sparsity pattern rather than completely restructuring it into a denser representation.

Pruning policies may also incorporate structural rules, such as keeping certain critical entries (e.g., diagonal entries) even if they are small.

6.2 Dropping small entries: tradeoffs and error bounds (practical)

Dropping small entries reduces nonzeros but introduces approximation error. Practical error analysis is often framed in terms of perturbation: the modified matrix equals the original plus a sparse perturbation whose magnitude is controlled by the threshold. In real implementations, practitioners monitor resulting residuals and solver performance to validate that dropped entries do not cause unacceptable degradation.

Tradeoffs include:

Lower memory and faster operations versus
Potential loss of diagonal dominance, reduced effective rank, or slower convergence.

Because theoretical guarantees depend on assumptions rarely perfectly met in practice, preprocessing often pairs pruning with validation checks.

6.3 Enforcing structural properties required by solvers

Some solvers require specific structural features, such as:

Existence of diagonal entries for preconditioners that use them,
Specific sign patterns or symmetry properties,
Compatible sparsity patterns for block operations.

Preprocessing enforces these properties by adding missing structural entries with default values, symmetrizing patterns, or adjusting the representation to match solver expectations.

6.4 Handling missing diagonals and diagonal dominance heuristics

Missing diagonal entries can cause breakdown in diagonal-based preconditioners or lead to instability in certain factorization variants. Preprocessing detects absent diagonals and may insert small stabilizing values or reconstruct diagonal entries from related data, depending on the model and the allowed modifications.

Diagonal dominance heuristics can guide additional pruning or scaling decisions, but they require caution: dominance may not reflect true spectral properties, and overly aggressive heuristics can harm solution quality.

7 Conditioning-oriented modifications

7.1 Diagonal regularization (conceptual overview)

Diagonal regularization modifies the operator to mitigate near-singularity or extreme conditioning. Conceptually, it adds a scaled identity (or related diagonal term) so that the matrix becomes better behaved for inversion-like operations. This can be interpreted as adding a mild penalty that stabilizes computations.

In preprocessing workflows, regularization is often optional and parameter-dependent. Its effects are evaluated through residual behavior and convergence diagnostics rather than by a one-size-fits-all rule.

7.2 Shifts for near-singularity cases

Shifts are similar in spirit to regularization but may be motivated by detecting problematic spectral behavior. A common preprocessing response to near-singular systems is to apply a shift that improves solvability for direct or iterative methods. The chosen shift aims to balance stability against bias introduced into the system.

Careful integration with the solver is needed so that any variable interpretation or back-transformation remains consistent.

7.3 Preconditioner compatibility considerations

Conditioning modifications affect preconditioners, especially those derived from the matrix structure (e.g., incomplete factorizations or algebraic multilevel components). Preprocessing therefore considers whether the preconditioner should reflect the modified operator or the original one.

Compatibility also includes parameter coupling: a threshold used for dropping entries in incomplete factorization may need retuning after scaling or regularization changes magnitudes. Good practice is to integrate conditioning modifications into a coherent pipeline rather than applying them as independent steps.

8 Graph-based augmentation and constraints

8.1 Building auxiliary graphs for ordering/analysis

Even when the original task is numerical, graph interpretations can drive ordering and analysis. Preprocessing may construct auxiliary graphs that represent the symmetrized adjacency, elimination dependencies, or fill-in estimates.

Auxiliary graphs also help with diagnosing issues such as highly disconnected components or bottlenecks in traversal. The additional structures are usually lightweight compared with the matrix itself but can significantly influence ordering quality.

8.2 Handling disconnected components

Some sparse matrices correspond to systems with multiple disconnected variable groups, where couplings between components are absent or negligible. Preprocessing can detect disconnected components and handle them separately. This can reduce factorization cost, enable independent processing, and improve parallel scalability.

In iterative solvers, disconnectedness can manifest as nullspaces or multiple solution components, so preprocessing may also prepare the solver for rank-deficient or underdetermined behavior.

8.3 Constraint matrix preprocessing (e.g., fixing reference variables)

When constraints exist, preprocessing may augment or transform the constraint matrix so it aligns with the solver’s formulation. A typical example is fixing a reference variable to remove an arbitrary additive degree of freedom. This ensures that the constrained system becomes solvable under the chosen formulation.

Constraint preprocessing also includes matching dimensions, applying consistent permutations, and ensuring the constraints integrate correctly with any scaling or elimination ordering.

8.4 Relating preprocessing to nullspaces and rank deficiency

Rank deficiency and nullspaces often depend on structural and numerical aspects of the matrix. Preprocessing steps such as reordering and scaling should preserve the mathematical nullspace structure (or transform it predictably) if the solver expects that behavior.

When preprocessing adds regularization or applies constraints, it effectively changes the nullspace or removes ambiguity. The pipeline therefore tracks how such changes alter the interpretation of solutions, residuals, and convergence criteria.

9 Format conversion and interoperability

9.1 Choosing a storage format for each phase

Sparse preprocessing commonly selects different formats for different tasks. COO is convenient for ingesting and cleaning; CSR or CSC is typical for row- or column-oriented kernels; block formats can reduce overhead when blocks are present. The goal is to minimize data movement while maximizing kernel efficiency.

Interoperability is also important: some libraries provide optimized routines only for particular formats or index arrangements. Preprocessing schedules conversions so they occur only when necessary.

9.2 Converting between COO, CSR, and CSC

Conversion operations reorder data and build indexing arrays. For COO-to-CSR, preprocessing sorts by row and builds row pointer offsets; for CSR-to-COO it expands indices back into coordinate lists. COO-to-CSR is often preceded by canonicalization so duplicates are merged before building compressed row pointers.

Correct conversion requires careful handling of:

Index uniqueness and sortedness,
Stable accumulation if duplicates exist,
Preserving symmetry structure if relevant to downstream assumptions.

9.3 Block formats (e.g., BSR) and when they help

Block sparse row (BSR) stores entries in fixed-size blocks, exploiting locality when nonzeros cluster in block patterns. BSR can reduce indexing overhead and improve performance for operations that operate blockwise, such as certain preconditioners or multi-vector operations.

Preprocessing may detect block structure based on index patterns or known modeling structures. If block sizes are chosen well, BSR improves throughput; if chosen poorly, it can inflate storage and harm performance.

9.4 Alignment and batching for performance

Performance-oriented preprocessing may align data structures to hardware-friendly boundaries or batch multiple operations to reduce overhead. For example, if the pipeline applies the same permutation and scaling to several right-hand sides, it can reuse metadata and avoid repeated conversions.

These optimizations are especially relevant in high-throughput pipelines where preprocessing cost can become significant relative to solve cost.

10 Factorization and solver preparation

10.1 Preparing for incomplete factorization

Incomplete factorization methods require preprocessing to set parameters like fill levels, drop tolerances, and pivot strategies. Preprocessing also prepares the matrix structure so symbolic analysis can estimate fill-in and allocate memory.

Because incomplete factorization is sensitive to scaling and sparsity dropping, preprocessing often applies scaling and pruning before symbolic setup, then uses consistency checks to ensure the incomplete factors can be built without failure.

10.2 Estimating fill-in and memory before factorization

Direct and incomplete factorization typically involve a symbolic phase that predicts how many nonzeros will appear in factors. Preprocessing contributes by improving ordering quality and by tightening sparsity patterns, both of which influence fill-in estimates.

Memory estimation is crucial for avoiding out-of-memory errors and for choosing parameters like maximum fill or level-of-fill. Preprocessing may also compute upper bounds or approximate forecasts to guide allocation strategies.

10.3 Schur complement or elimination-based preprocessing (high level)

Some solver workflows construct Schur complements or perform elimination steps to reduce the effective problem size. Preprocessing helps by identifying elimination order, isolating variables to eliminate, and preparing the remaining submatrix and coupling terms.

At a high level, such preprocessing requires tracking which variables are removed, how constraints are applied, and how the reduced operator relates back to the original system so that reconstruction is possible if needed.

10.4 Partitioning strategies for parallel execution

Parallel factorization and iterative methods benefit from partitioning the graph of the matrix into subdomains. Preprocessing may run graph partitioners and convert partitions into data layouts that minimize communication.

Partition quality impacts both load balance and fill-in in distributed elimination. Preprocessing therefore integrates partitioning with ordering choices and with the solver’s communication model, aiming to reduce synchronization and bandwidth demands.

11 Preconditioning workflow integration

11.1 When preprocessing overlaps with preconditioner setup

Preconditioning can require some of the same preprocessing steps as the solver itself. For instance, ordering and scaling influence how preconditioners are constructed, while format conversion affects kernel execution for applying the preconditioner.

Rather than treating preprocessing and preconditioner setup as separate black boxes, a unified workflow shares intermediate results—such as permutation vectors, scaled values, and structural metadata—to avoid redundant work.

11.2 Pipeline design: ordering → scaling → format → preconditioner

A common pipeline sequence is:

Ordering to reduce fill-in and improve locality.
Scaling to improve numerical behavior.
Format conversion to match storage expectations of kernels and preconditioner builders.
Preconditioner construction that consumes the prepared matrix.

Exact ordering of steps can vary. For example, some preprocessing tasks require canonicalization before ordering can be computed. Nonetheless, the pipeline is designed so that each step produces outputs directly used by the next.

11.3 Parameter selection and automatic tuning hooks

Preconditioning often depends on parameters such as drop tolerances, levels of fill, and scaling modes. Preprocessing can include hooks for automatic tuning based on matrix statistics—like average row length, estimated condition proxies, or detected symmetry/block structure.

Tuning may be guided by constraints on runtime budget, memory limits, and target solver behavior. Some systems run lightweight probes to choose parameters, then rebuild the preconditioner accordingly.

12 Validation, debugging, and reproducibility

12.1 Verifying structural invariants after transformations

After each transformation, preprocessing can validate invariants such as:

Dimensions consistency between matrix and vectors,
Correct application of permutations,
Symmetry preserved when assumed,
Uniqueness of indices after canonicalization.

Structural checks are often cheap relative to the cost of failure in later stages. They are also essential when preprocessing includes conditional steps like pruning or diagonal insertion.

12.2 Numerical checks: residuals and consistency tests

Preprocessing validation includes numerical diagnostics. Typical tests compute residual norms for a small solve or verify that transformation relations hold (e.g., applying permutations and scaling yields consistent operator action). For pipelines that modify the matrix, checks also compare solver outcomes against expected behavior, such as monotonic residual reduction in iterative methods.

For pruning and regularization steps, validation can track how much the operator changed and whether the modified system remains within acceptable accuracy bounds.

12.3 Determinism and floating-point effects

Some preprocessing operations—especially those involving parallel merging, hashing, or reductions—can be nondeterministic due to floating-point summation order. This can lead to small numerical differences that may affect convergence in sensitive problems.

If determinism is required, preprocessing uses deterministic sorting/accumulation strategies, stable merge orders, or fixed reduction patterns. It also records the relevant metadata so results can be reproduced.

12.4 Logging permutation/scaling metadata for auditability

Auditability is important for debugging and for comparing experiments. Preprocessing logs include:

Permutation vectors or hashes,
Scaling factors and their computation mode,
Thresholds used for pruning or regularization,
Format conversions and data layout parameters.

A well-instrumented pipeline allows developers to trace solver behavior back to preprocessing decisions, facilitating targeted fixes.

13 Performance considerations and benchmarking

13.1 Memory traffic vs arithmetic intensity

Preprocessing often changes memory access patterns more than arithmetic work. Sparse operations are frequently memory-bandwidth limited, so improving locality and reducing nonzeros can have an outsized effect on runtime.

Benchmarking considers both absolute preprocessing time and its effect on downstream memory traffic. A preprocessing step that slightly increases preprocessing overhead may still be worthwhile if it reduces fill-in or improves cache behavior during solves.

13.2 Cache locality and traversal order

Reordering affects how indices and values are laid out. Good locality can reduce cache misses during repeated operations such as sparse matrix-vector products and triangular solves. Preprocessing that results in shorter, more clustered row segments can also reduce indirect indexing overhead.

Additionally, format conversion may influence whether traversal uses contiguous memory. CSR and CSC differ in access patterns, and the choice should match the dominant kernel directions.

13.3 Benchmarking methodology and baselines

Effective benchmarking compares against relevant baselines:

Solver runtime without preprocessing,
Preprocessing variants with identical downstream solver settings,
Parameter sweeps for ordering/scaling/pruning to separate cause and effect.

Benchmarking also measures end-to-end metrics including setup time, per-iteration cost, iteration counts, and total solve time. For fair comparisons, it should account for the number of right-hand sides, reuse of preconditioners, and amortization of preprocessing over multiple solves.

13.4 Parallel and distributed preprocessing considerations

In parallel settings, preprocessing can be constrained by communication and synchronization. Canonicalization and duplicate merging may require global sorting or distributed aggregation. Reordering and graph partitioning often involve nontrivial communication patterns as well.

Scalability studies assess how preprocessing time grows with problem size and process count. Good preprocessing design aims to keep communication volume low, reuse computed structures across tasks, and avoid repeated global passes when possible.