Abstract
We discuss the design and implementation of a suite of test matrix generators for testing linear algebra software. These routines generate random matrices with certain properties which are useful for testing linear equation solving, least squares, and eigendecomposition software. These properties include the spectrum, symmetry, bandwidth, norm, sparsity, conditioning (with respect to inversion or for the eigenproblem), type (real or complex), and storage scheme (dense, packed or banded).
Introduction
The development of robust numerical libraries like LAPACK requires rigorous testing beyond "typical" or well-behaved cases. To ensure reliability, algorithms must be evaluated against pathological matrices—those that are nearly singular, possess specific symmetries, or exhibit unusual eigenvalue distributions (spectra).
Manually constructing these edge cases is both tedious and prone to error. Furthermore, verifying consistency across different memory layouts (e.g., dense, packed, or banded) necessitates a method to generate mathematically identical matrices in various storage formats. This paper introduces a standardized, automated suite of Fortran 77 routines to address these challenges, providing a foundation for verifying linear equation solvers, least squares routines, and eigendecomposition algorithms.
Methodology
The suite consists of three primary routines, prefixed by x to denote supported data types (Single, Double, Complex, or Double Complex):
xLATMR: Optimized for speed, this routine generates matrices with random off-diagonal entries and a user-specified diagonal. It is particularly efficient for large banded matrices as it avoids full-matrix transformations.xLATMS: A precision-oriented tool that allows users to specify the exact eigenvalues for symmetric matrices or singular values for nonsymmetric matrices. It employs Householder transformations to reduce a dense matrix to a target bandwidth while preserving the requested spectrum.xLATME: Specialized for nonsymmetric eigenproblems, this routine provides control over the Jordan form (enabling the creation of "defective" matrices) and the conditioning (sensitivity) of the eigenvalues.
A significant technical contribution is the implementation of Stewart’s method for generating truly random orthogonal and unitary matrices. These are essential for performing similarity transformations that do not introduce bias into the resulting test matrices.
Synthetic Data Generation
Rather than relying on external datasets, this suite serves as a factory for synthetic data. It enables the generation of matrices that mimic a wide array of real-world numerical difficulties. By providing a reproducible source of "difficult" matrices, it establishes a benchmark for evaluating the stability and accuracy of new linear algebra routines.
Key Design Principles
The suite is built on several core principles to maximize its utility for software testing:
- Controlled Difficulty: Users can specify constraints such as a condition number of $10^{12}$, which is vital for testing how solvers handle near-singular systems.
- Storage Consistency: The ability to generate the same mathematical matrix in different storage schemes allows developers to verify that specialized solvers (e.g., banded) produce results identical to general-purpose (dense) solvers.
- Distribution Flexibility: The underlying probability distribution for random entries can be selected by the user, including Uniform, Normal, or uniform distributions on a complex disk.
- Bandwidth Constraints: The software accounts for mathematical limitations; for instance, it is not always possible to specify both a spectrum and an arbitrary bandwidth for nonsymmetric matrices. The routines explicitly check for such consistency errors.
Performance and Robustness
The suite was designed with both efficiency and extreme-case testing in mind:
- Efficiency: The
xLATMRroutine operates in $O(\text{bandwidth} \times N)$ time, facilitating the testing of very large systems. - Numerical Edge Cases: Routines include options to scale matrices near the overflow and underflow thresholds of computer arithmetic, testing the limits of numerical stability.
- Reproducibility: By utilizing a 24-bit integer seed for the random number generator, the suite ensures that specific test cases can be exactly reproduced across different computing environments.
Limitations and Conclusion
While powerful, the suite has inherent limitations. The use of dense orthogonal transformations in xLATMS and xLATME introduces rounding errors. If a user requests eigenvalues significantly smaller than the machine epsilon $\epsilon$, the actual eigenvalues of the generated matrix may deviate by approximately $\epsilon \times \|A\|$. Additionally, generating nontrivial random nonsymmetric matrices with a specific spectrum and arbitrary upper/lower bandwidths remains an open challenge.
Despite these constraints, LAPACK Working Note 9 established the standard testing infrastructure for LAPACK and subsequent libraries like ScaLAPACK, ensuring that modern numerical software is resilient against the complexities of real-world data.
Summary updated