Summary
tensor_pseudoinverse() passes the wrong inner dimension to cblas_dgemm. For any matrix with
more rows than columns it reads past the end of the n × n right singular vectors. The result is
silently wrong for small matrices, entirely non-finite for larger ones, and dependent on unrelated
heap state in between — so the same input can produce different output in different programs.
Affects master (b197cbe). Found while building a parity harness: the operation produced
different results on two consecutive runs of the same script.
Reproduction
<?php
// A 500x2 matrix. Nothing about the values matters.
mt_srand(11);
$samples = [];
for ($i = 0; $i < 500; ++$i) {
$samples[] = [mt_rand(-1000, 1000) / 100, mt_rand(-1000, 1000) / 100];
}
$a = Tensor\Matrix::quick($samples);
$p = $a->pseudoinverse();
$nonFinite = 0;
foreach ($p->asArray() as $row) {
foreach ($row as $value) {
if (!is_finite($value)) {
++$nonFinite;
}
}
}
echo "non-finite elements: {$nonFinite} of 1000\n"; // 1000 of 1000
The first Moore-Penrose condition fails with it:
| A |
max abs(A·A⁺·A − A) |
| 2×3 |
5.3e-15 |
| 100×4 |
1.2e-14 |
| 500×2 |
all elements non-finite |
| 2×500 |
7.1e-15 |
Scanning m for each n, the first shape that produces non-finite output is m = 203 at n = 2 and
m = 151 at n = 3. Below those thresholds the read still goes out of bounds; it just lands on
memory that happens to be mapped, so the answer looks plausible.
Cause
ext/include/linear_algebra.c, in tensor_pseudoinverse():
cblas_dgemm(CblasRowMajor, CblasTrans, CblasTrans, n, m, m, 1.0, vvt, n, vu, m, 0.0, vb, m);
/* K ---^ */
K is the inner dimension of the product. With CblasTrans on the first operand, CBLAS reads it
as K × M — here m rows of n — but vvt is only n × n, as allocated twenty lines above and
as LAPACKE_dgesdd filled it. Every call with m > n therefore reads (m − n) × n doubles past
the end of the buffer.
The correct inner dimension is the rank of the thin SVD, k = MIN(m, n), which the function
already computes. It happens to equal m for square and wide matrices, which is why the existing
2×3 test passes.
Fix
- cblas_dgemm(CblasRowMajor, CblasTrans, CblasTrans, n, m, m, 1.0, vvt, n, vu, m, 0.0, vb, m);
+ cblas_dgemm(CblasRowMajor, CblasTrans, CblasTrans, n, m, k, 1.0, vvt, n, vu, m, 0.0, vb, m);
The leading dimensions are already right: lda = n selects the first k rows of vvt, and
ldb = m selects the first k columns of vu.
With the fix, every shape tried satisfies A·A⁺·A = A to ~1e-14, including 500×2, 203×2, 151×3,
600×2 and 1000×3. The existing suite stays green.
Note on test coverage
MatrixTest::pseudoinverse() carries @requires extension tensor, but the extension is named
tensor_ext. That test, and three others (eig, eigSymmetric, svd), have therefore been
skipped rather than run since the rename. Fixing the annotation is a separate one-line change and
is what makes this bug testable.
Summary
tensor_pseudoinverse()passes the wrong inner dimension tocblas_dgemm. For any matrix withmore rows than columns it reads past the end of the
n × nright singular vectors. The result issilently wrong for small matrices, entirely non-finite for larger ones, and dependent on unrelated
heap state in between — so the same input can produce different output in different programs.
Affects
master(b197cbe). Found while building a parity harness: the operation produceddifferent results on two consecutive runs of the same script.
Reproduction
The first Moore-Penrose condition fails with it:
max abs(A·A⁺·A − A)Scanning m for each n, the first shape that produces non-finite output is m = 203 at n = 2 and
m = 151 at n = 3. Below those thresholds the read still goes out of bounds; it just lands on
memory that happens to be mapped, so the answer looks plausible.
Cause
ext/include/linear_algebra.c, intensor_pseudoinverse():Kis the inner dimension of the product. WithCblasTranson the first operand, CBLAS reads itas
K × M— heremrows ofn— butvvtis onlyn × n, as allocated twenty lines above andas
LAPACKE_dgesddfilled it. Every call withm > ntherefore reads(m − n) × ndoubles pastthe end of the buffer.
The correct inner dimension is the rank of the thin SVD,
k = MIN(m, n), which the functionalready computes. It happens to equal
mfor square and wide matrices, which is why the existing2×3 test passes.
Fix
The leading dimensions are already right:
lda = nselects the firstkrows ofvvt, andldb = mselects the firstkcolumns ofvu.With the fix, every shape tried satisfies
A·A⁺·A = Ato ~1e-14, including 500×2, 203×2, 151×3,600×2 and 1000×3. The existing suite stays green.
Note on test coverage
MatrixTest::pseudoinverse()carries@requires extension tensor, but the extension is namedtensor_ext. That test, and three others (eig,eigSymmetric,svd), have therefore beenskipped rather than run since the rename. Fixing the annotation is a separate one-line change and
is what makes this bug testable.