tensor/linalg/sparselsqr.go

// Copyright (c) 2026 Petr Balvín <opensource@petrbalvin.org> (https://petrbalvin.org)
// SPDX-License-Identifier: MIT

package linalg

import (
	"math"

	"sourcedock.dev/petrbalvin/tensor/internal/base"
	"sourcedock.dev/petrbalvin/tensor/internal/core"
)

// Overdetermined sparse least squares: min ‖A·x − b‖₂ for a sparse A
// with at least as many rows as columns. The dense `LeastSquares`
// factorises the whole matrix, which a large sparse system cannot
// afford and need not: LSQR and LSMR walk the Golub-Kahan
// bidiagonalisation instead, whose every step costs one A·v product
// and one Aᵀ·u product, so the cost tracks the non-zero count. LSQR
// minimises ‖b − A·x‖ over the growing Krylov space; LSMR minimises
// ‖Aᵀ(b − A·x)‖, which keeps the normal-equations residual monotone.
//
// Both solvers carry the stopping-criterion trio the roadmap names for
// this recursion (Paige and Saunders):
//
//   - "residual": the estimate of ‖b − A·x‖₂ has fallen against the
//     scaled target tol·(‖b‖ + ‖A‖·‖x‖);
//   - "normal": the estimate of ‖Aᵀ(b − A·x)‖₂, the residual of the
//     normal equations, has fallen against tol·‖A‖·‖b − A·x‖;
//   - "condition": the iteration's conditional estimate of cond(A)
//     has passed the limit conlim, the augmented estimate the
//     recursion maintains from the bidiagonal entries.
//
// The iteration stops when ANY criterion fires, the standard LSQR and
// LSMR semantics, and the returned info records which one fired. When
// several fire on the same step the residual criterion wins, the
// priority the reference implementations apply. A condition stop is a
// stop, not a convergence, and Converged reports the difference.
//
// An underdetermined system (fewer rows than columns) is refused: the
// problem changes shape there, the minimum-norm answer of an
// underdetermined solve is a different contract than the least-squares
// answer this file implements, and the dense surface refuses it the
// same way.
//
// Both entry points are deterministic: every product runs serially
// over the stored entries in index order and no goroutine joins the
// iteration. The per-step allocation is nothing beyond the info's own
// estimate trajectory: the working vectors are allocated once and
// reused, and no step copies a matrix.
//
// Two guards keep the recursion honest where the plain recurrences
// would lie. A bidiagonal entry at or below 64·eps of the recursion's
// own scale, the constant `SolveTruncated` applies to a vanished
// singular value, carries no usable direction: it is treated as
// exactly zero, the current step folds on the clamped values and the
// iteration stops, because a direction the recursion cannot resolve
// would otherwise be amplified into the answer. And a fired criterion
// is verified against the explicitly recomputed residual before the
// answer is returned, so an estimate the drift of the recursion has
// detached from the truth can end the iteration only as an honest
// failure, never as a converged answer.

// spLeastSquaresTol is the default relative tolerance when the caller
// passes zero, matching the package's iterative solvers.
const spLeastSquaresTol = 1e-10

// spLeastSquaresConLim is the default condition limit when the caller
// passes zero: large enough that a healthy system never trips it, low
// enough that a hopeless one stops instead of burning its budget.
const spLeastSquaresConLim = 1e8

// spLeastSquaresBreakdown is the breakdown constant, in multiples of
// the machine epsilon relative to the recursion's own scale, below
// which a bidiagonal entry is treated as exactly zero.
const spLeastSquaresBreakdown = 64

// The stopping criteria a sparse least-squares iteration can report.
const (
	// LeastSquaresResidual names the residual-norm criterion: the
	// estimate of ‖b − A·x‖₂ met the scaled target.
	LeastSquaresResidual = "residual"
	// LeastSquaresNormal names the normal-equations criterion: the
	// estimate of ‖Aᵀ(b − A·x)‖₂ met the scaled target.
	LeastSquaresNormal = "normal"
	// LeastSquaresCondition names the conditional criterion: the
	// estimate of cond(A) passed the limit.
	LeastSquaresCondition = "condition"
)

// LeastSquaresInfo reports what a sparse least-squares iteration
// achieved and which stopping test ended it.
type LeastSquaresInfo struct {
	// Iterations is the number of Golub-Kahan steps folded into the
	// answer.
	Iterations int
	// Criterion names the test that ended the iteration:
	// LeastSquaresResidual, LeastSquaresNormal or
	// LeastSquaresCondition. It is empty when the exact answer x = 0
	// was returned without a step.
	Criterion string
	// ResidualNorm is the achieved ‖b − A·x‖₂, recomputed explicitly
	// from the returned x once the iteration has ended, so it is the
	// truth and not the in-loop estimate.
	ResidualNorm float64
	// NormalResidual is the achieved ‖Aᵀ(b − A·x)‖₂, recomputed the
	// same way.
	NormalResidual float64
	// MatrixNorm is the iteration's running estimate of ‖A‖.
	MatrixNorm float64
	// Condition is the iteration's running estimate of cond(A).
	Condition float64
	// Converged reports whether a residual or normal-equations test
	// fired. A condition stop leaves it false: the answer is the
	// estimate reached when the condition limit passed, the standard
	// LSQR and LSMR semantics, and an honest caller treats it as a
	// warning, not a solution.
	Converged bool

	// residualEstimates and normalEstimates hold the per-step in-loop
	// estimates of ‖b − A·x‖ and ‖Aᵀ(b − A·x)‖ in iteration order, so
	// the convergence behaviour stays inspectable.
	residualEstimates []float64
	normalEstimates   []float64
}

// lsqrOperator holds A and its transpose in CSR form, built once per
// solve so every iteration streams two products through contiguous
// slices instead of touching the coordinate form.
type lsqrOperator struct {
	m, n     int
	rowStart []int
	colIdx   []int
	vals     []float64
	tStart   []int
	tIdx     []int
	tVals    []float64
}

// newLSQROperator converts the coordinate form through the canonical
// CSR conversion (duplicates sum, explicit zeros drop) and counts the
// transpose in one pass.
func newLSQROperator(a *core.SparseCOO) (*lsqrOperator, error) {
	csr, err := CSRFromCOO(a)
	if err != nil {
		return nil, err
	}
	t := csr.Transpose()
	return &lsqrOperator{
		m: csr.Rows, n: csr.Cols,
		rowStart: csr.RowStart, colIdx: csr.ColIdx, vals: csr.Values,
		tStart: t.RowStart, tIdx: t.ColIdx, tVals: t.Values,
	}, nil
}

// matVec writes A·x into out, one row at a time in ascending order.
func (op *lsqrOperator) matVec(x, out []float64) {
	for i := range op.m {
		sum := 0.0
		for p := op.rowStart[i]; p < op.rowStart[i+1]; p++ {
			sum += op.vals[p] * x[op.colIdx[p]]
		}
		out[i] = sum
	}
}

// tMatVec writes Aᵀ·x into out, one column of A at a time in ascending
// order, which keeps the reduction order deterministic.
func (op *lsqrOperator) tMatVec(x, out []float64) {
	for j := range op.n {
		sum := 0.0
		for p := op.tStart[j]; p < op.tStart[j+1]; p++ {
			sum += op.tVals[p] * x[op.tIdx[p]]
		}
		out[j] = sum
	}
}

// checkSparseLeastSquares validates the inputs both least-squares
// solvers share: a non-empty real 2-D sparse matrix with at least as
// many rows as columns and a real right-hand side of the row count. It
// returns the operator and b as a working vector.
func checkSparseLeastSquares(name string, a *core.SparseCOO, b *core.Array) (*lsqrOperator, []float64, error) {
	if a.Values.Dtype() == core.Complex {
		return nil, nil, base.Errf("%s: complex sparse matrices are not supported", name)
	}
	if len(a.Shape) != 2 || a.Shape[0] == 0 || a.Shape[1] == 0 {
		return nil, nil, base.Errf("%s: needs a non-empty 2-D sparse matrix, got shape %v", name, a.Shape)
	}
	m, n := a.Shape[0], a.Shape[1]
	if m < n {
		return nil, nil, base.Errf("%s: needs an overdetermined system with m ≥ n, got %d×%d; the underdetermined minimum-norm problem is a different contract", name, m, n)
	}
	op, err := newLSQROperator(a)
	if err != nil {
		return nil, nil, base.Errf("%s: %w", name, err)
	}
	if b.Dtype() == core.Complex {
		return nil, nil, base.Errf("%s: complex right-hand sides are not supported", name)
	}
	if b.NDim() != 1 || b.Len() != m {
		return nil, nil, base.Errf("%s: right-hand side must be a vector of length %d, got shape %s",
			name, m, base.ShapeText(b.Shape()))
	}
	return op, vectorF64(b, m), nil
}

// symOrtho computes the Givens rotation of the pair (a, b) that zeroes
// the second coordinate, in the stable form the reference
// implementations use: the signs are carried instead of cancelled, so
// no intermediate reaches 1/eps. r is the resulting non-negative norm.
func symOrtho(a, b float64) (c, s, r float64) {
	switch {
	case b == 0:
		return sign(a), 0, math.Abs(a)
	case a == 0:
		return 0, sign(b), math.Abs(b)
	case math.Abs(b) > math.Abs(a):
		tau := a / b
		s = sign(b) / math.Sqrt(1+tau*tau)
		c = s * tau
		r = b / s
	default:
		tau := b / a
		c = sign(a) / math.Sqrt(1+tau*tau)
		s = c * tau
		r = a / c
	}
	return c, s, r
}

// lsqrExplicitNorms recomputes ‖b − A·x‖ and ‖Aᵀ(b − A·x)‖ directly
// from a candidate x: two products, run once at the end of the
// iteration, so the reported achieved quantities are the truth rather
// than the in-loop estimates. ax and ar are scratch vectors of the
// operator's row and column counts, taken over from the iteration that
// just ended.
func lsqrExplicitNorms(op *lsqrOperator, bv, x, ax, ar []float64) (rNorm, arNorm float64) {
	op.matVec(x, ax)
	for i := range op.m {
		ax[i] = bv[i] - ax[i]
	}
	op.tMatVec(ax, ar)
	return norm2F64(ax), norm2F64(ar)
}

// verifyLeastSquares checks a fired criterion against the explicitly
// recomputed norms, with the round-off slack the achieved norms can
// never beat, and relabels to the sibling test when the fired one
// fails while the other passes. It reports whether the achieved
// answer satisfies any residual test at all; a condition stop makes no
// accuracy claim and passes unverified.
func verifyLeastSquares(criterion string, rNorm, arNorm, bNorm, matrixNorm, xNorm, tol float64) (string, bool) {
	targetR := tol*(bNorm+matrixNorm*xNorm) + 64*base.EpsF*(bNorm+matrixNorm*xNorm)
	targetA := tol*matrixNorm*rNorm + 64*base.EpsF*matrixNorm*(bNorm+rNorm+xNorm)
	passR := rNorm <= targetR
	passA := arNorm <= targetA
	switch criterion {
	case LeastSquaresResidual:
		if passR {
			return LeastSquaresResidual, true
		}
		if passA {
			return LeastSquaresNormal, true
		}
	case LeastSquaresNormal:
		if passA {
			return LeastSquaresNormal, true
		}
		if passR {
			return LeastSquaresResidual, true
		}
	default:
		return criterion, true
	}
	return criterion, false
}

// zeroLeastSquaresAnswer builds the answer both solvers give when the
// iteration needs no step: b is zero, or b is orthogonal to the column
// space of A, and x = 0 is then the exact least-squares solution.
func zeroLeastSquaresAnswer(n int, bNorm, alpha float64) (*core.Array, *LeastSquaresInfo, error) {
	x, err := core.Zeros(core.Float, n)
	if err != nil {
		return nil, nil, err
	}
	info := &LeastSquaresInfo{
		Criterion:      "",
		Converged:      true,
		ResidualNorm:   bNorm,
		NormalResidual: 0,
		MatrixNorm:     alpha,
		Condition:      0,
	}
	return x, info, nil
}

// SpLSQR returns the vector x minimising ‖A·x − b‖₂ over a sparse
// overdetermined A, by the Golub-Kahan bidiagonalisation recursion of
// Paige and Saunders. The stopping criterion trio is the residual-norm
// estimate, the normal-equations residual and the conditional
// estimate; the iteration stops when ANY criterion fires and the
// returned info names it and carries the achieved quantities.
//
// tol ≤ 0 means 1e-10 and feeds both the residual and the
// normal-equations test; maxIter ≤ 0 means 2n steps, the reference
// default of twice the Krylov dimension; conlim ≤ 0 means 1e8, and
// cond(A) passing it stops the iteration without claiming
// convergence. Running out of steps with every tolerance unmet is an
// error naming the residual achieved, with no estimate returned, in
// the style of the package's other solvers.
func SpLSQR(a *core.SparseCOO, b *core.Array, tol float64, maxIter int, conlim float64) (*core.Array, *LeastSquaresInfo, error) {
	const name = "SpLSQR"
	op, bv, err := checkSparseLeastSquares(name, a, b)
	if err != nil {
		return nil, nil, err
	}
	if tol <= 0 {
		tol = spLeastSquaresTol
	}
	if conlim <= 0 {
		conlim = spLeastSquaresConLim
	}
	ctol := 1 / conlim
	m, n := op.m, op.n
	if maxIter <= 0 {
		maxIter = 2 * n
	}

	x := make([]float64, n)
	bNorm := norm2F64(bv)
	if bNorm == 0 {
		return zeroLeastSquaresAnswer(n, 0, 0)
	}
	// β₁u₁ = b, α₁v₁ = Aᵀu₁. A vanishing α₁ means b is orthogonal to
	// the column space and x = 0 is the exact answer.
	u := append([]float64(nil), bv...)
	scale := 1 / bNorm
	for i := range m {
		u[i] *= scale
	}
	v := make([]float64, n)
	op.tMatVec(u, v)
	alpha := norm2F64(v)
	if alpha == 0 {
		return zeroLeastSquaresAnswer(n, bNorm, 0)
	}
	scale = 1 / alpha
	for j := range n {
		v[j] *= scale
	}
	w := append([]float64(nil), v...)

	// The rotated right-hand side: φ̄ carries the part of b no step has
	// consumed yet, ρ̄ the pending bidiagonal entry. The estimates are
	// ‖b − A·x‖ = |φ̄| and the normal-equations estimate α·|τ|, τ being
	// the rotated off-diagonal, exactly as the reference recursion
	// maintains them.
	rhobar, phibar := alpha, bNorm
	anorm, ddnorm, xxnorm := 0.0, 0.0, 0.0
	xnorm, z, cs2, sn2 := 0.0, 0.0, -1.0, 0.0
	info := &LeastSquaresInfo{}
	criterion := ""
	exhausted := false
	steps := 0
	uBuf := make([]float64, m)
	vBuf := make([]float64, n)
	// The per-step estimates grow into buffers sized for the iteration
	// budget, capped at the default budget so a caller's huge maxIter
	// cannot allocate steps the recursion will not take.
	estCap := min(maxIter, 2*n)
	rEsts := make([]float64, 0, estCap)
	arEsts := make([]float64, 0, estCap)
	// hScale tracks the recursion's own magnitude for the breakdown
	// floor: a bidiagonal entry at round-off of the scale already seen
	// carries no direction.
	hScale := max(alpha, bNorm)

	// hitBudget tells the three exits apart: a loop that ended by its
	// own iteration count fired no criterion and broke down nowhere,
	// which is the budget's fault and not an estimate's drift.
	hitBudget := true
	for itn := 1; itn <= maxIter; itn++ {
		// βu = A·v − αu, αv = Aᵀu − βv: one step of the bidiagonalisation.
		op.matVec(v, uBuf)
		for i := range m {
			uBuf[i] -= alpha * u[i]
		}
		if !vecFinite(uBuf) {
			return nil, nil, base.Errf("%s: non-finite residual direction at step %d", name, itn)
		}
		beta := norm2F64(uBuf)
		hScale = max(hScale, beta)
		floor := spLeastSquaresBreakdown * base.EpsF * hScale
		if beta <= floor {
			// The u-direction is gone: fold the pending step as the
			// exact-arithmetic completion, with β = 0, and stop.
			beta = 0
			exhausted = true
		} else {
			scale = 1 / beta
			for i := range m {
				u[i] = uBuf[i] * scale
			}
			anorm = math.Sqrt(anorm*anorm + alpha*alpha + beta*beta)
			op.tMatVec(u, vBuf)
			for j := range n {
				vBuf[j] -= beta * v[j]
			}
			if !vecFinite(vBuf) {
				return nil, nil, base.Errf("%s: non-finite normal direction at step %d", name, itn)
			}
			alpha = norm2F64(vBuf)
			hScale = max(hScale, alpha)
			if alpha <= floor {
				// The v-direction is gone: α is the exact zero the
				// recursion would have produced, v the zero vector, and
				// the iteration stops after this fold.
				alpha = 0
				exhausted = true
				clear(v)
			} else if alpha > 0 {
				scale = 1 / alpha
				for j := range n {
					v[j] = vBuf[j] * scale
				}
			}
		}
		// The plane rotation that eliminates the subdiagonal β. With a
		// clamped β the rotation reads zero off the subdiagonal, which
		// is the exact-arithmetic completion of the recursion; a stale
		// α only feeds ᾱ, which the stop leaves unused.
		cs, sn, rho := symOrtho(rhobar, beta)
		if rho == 0 {
			exhausted = true
			hitBudget = false
			break
		}
		theta := sn * alpha
		rhobar = -cs * alpha
		phi := cs * phibar
		phibar = sn * phibar
		tau := sn * phi
		t1 := phi / rho
		t2 := -theta / rho
		// ddnorm feeds the condition estimate: the accumulated squared
		// lengths of the consumed directions, read before w moves.
		nw := norm2F64(w)
		ddnorm += nw * nw / (rho * rho)
		for j := range n {
			x[j] += t1 * w[j]
			w[j] = v[j] + t2*w[j]
		}
		steps = itn
		// ‖x‖ through a running rotation on the triangular solve, the
		// reference recursion's incremental form. cs2 starts at −1 and
		// every update carries a nonzero gambar, so the divisions never
		// see zero.
		delta := sn2 * rho
		gambar := -cs2 * rho
		rhs := phi - delta*z
		zbar := rhs / gambar
		xnorm = math.Sqrt(xxnorm + zbar*zbar)
		gamma := math.Hypot(gambar, theta)
		cs2 = gambar / gamma
		sn2 = theta / gamma
		z = rhs / gamma
		xxnorm += z * z

		rEst := math.Abs(phibar)
		arEst := alpha * math.Abs(tau)
		rEsts = append(rEsts, rEst)
		arEsts = append(arEsts, arEst)
		acond := anorm * math.Sqrt(ddnorm)
		test1 := rEst / bNorm
		test2 := arEst / (anorm*rEst + base.EpsF)
		test3 := 1 / (acond + base.EpsF)
		target := tol * (1 + anorm*xnorm/bNorm)
		switch {
		case test1 <= target:
			criterion = LeastSquaresResidual
		case test2 <= tol:
			criterion = LeastSquaresNormal
		case test3 <= ctol:
			criterion = LeastSquaresCondition
		}
		if criterion != "" || exhausted {
			hitBudget = false
			break
		}
	}

	rNorm, arNorm := lsqrExplicitNorms(op, bv, x, uBuf, vBuf)
	criterion = settleLeastSquares(criterion, exhausted, rNorm, arNorm, x, bNorm, anorm, tol)
	if criterion == "" {
		if exhausted {
			return nil, nil, base.Errf("%s: no convergence: the recursion folded at step %d, residual %.3g (tolerance %.3g)",
				name, steps, rNorm, tol)
		}
		if hitBudget {
			return nil, nil, base.Errf("%s: no convergence in %d steps, residual %.3g (tolerance %.3g)",
				name, maxIter, rNorm, tol)
		}
		return nil, nil, base.Errf("%s: a stopping criterion fired at step %d but its estimate drifted past the recomputed norms (residual %.3g, tolerance %.3g)",
			name, steps, rNorm, tol)
	}
	info.Iterations = steps
	info.Criterion = criterion
	info.Converged = criterion != LeastSquaresCondition
	info.ResidualNorm = rNorm
	info.NormalResidual = arNorm
	info.MatrixNorm = anorm
	info.Condition = anorm * math.Sqrt(ddnorm)
	info.residualEstimates = rEsts
	info.normalEstimates = arEsts
	return floatsToArray(x, []int{n}), info, nil
}

// SpLSMR returns the vector x minimising ‖Aᵀ(b − A·x)‖₂ over a sparse
// overdetermined A, by Fong and Saunders' LSMR, the Golub-Kahan
// bidiagonalisation with the recurrences reorganised so that both
// ‖b − A·x‖ and ‖Aᵀ(b − A·x)‖ carry exact-norm estimates. The stopping
// criterion trio and the reporting contract are SpLSQR's; the
// normal-equations residual, LSMR's own minimisation target, moves
// monotonically. LSMR's answer on a consistent rank-deficient system
// is the minimum-norm one, as LSQR's is.
//
// maxIter ≤ 0 means 2n steps, twice the Krylov dimension, the same
// default SpLSQR applies; the breakdown floor ends the recursion
// before a step can fold a direction the space cannot resolve.
func SpLSMR(a *core.SparseCOO, b *core.Array, tol float64, maxIter int, conlim float64) (*core.Array, *LeastSquaresInfo, error) {
	const name = "SpLSMR"
	op, bv, err := checkSparseLeastSquares(name, a, b)
	if err != nil {
		return nil, nil, err
	}
	if tol <= 0 {
		tol = spLeastSquaresTol
	}
	if conlim <= 0 {
		conlim = spLeastSquaresConLim
	}
	ctol := 1 / conlim
	m, n := op.m, op.n
	if maxIter <= 0 {
		maxIter = 2 * n
	}

	x := make([]float64, n)
	bNorm := norm2F64(bv)
	if bNorm == 0 {
		return zeroLeastSquaresAnswer(n, 0, 0)
	}
	u := append([]float64(nil), bv...)
	scale := 1 / bNorm
	for i := range m {
		u[i] *= scale
	}
	v := make([]float64, n)
	op.tMatVec(u, v)
	alpha := norm2F64(v)
	if alpha == 0 {
		return zeroLeastSquaresAnswer(n, bNorm, 0)
	}
	scale = 1 / alpha
	for j := range n {
		v[j] *= scale
	}

	// The two rotation pairs of LSMR: one turns the bidiagonal matrix
	// upper triangular (ρ, c, s and the ᾱ carry), the other turns its
	// transpose back (c̄, s̄, ρ̄), which is what makes ζ̄ the exact
	// normal-equations norm the solver minimises.
	zetabar := alpha * bNorm
	alphabar := alpha
	rho, rhobar := 1.0, 1.0
	cbar, sbar := 1.0, 0.0
	h := append([]float64(nil), v...)
	hbar := make([]float64, n)

	// The residual-norm bookkeeping: ζ, βd and β̆ walk the rotated
	// right-hand side so ‖r‖ = √((βd − τd)² + β̆²) is exact in exact
	// arithmetic.
	betadd, betad := bNorm, 0.0
	rhodold, tautildeold, thetatilde, zeta := 1.0, 0.0, 0.0, 0.0

	// The ‖A‖ and cond(A) estimates: the squared bidiagonal entries and
	// the extreme rotated diagonals.
	normA2 := alpha * alpha
	maxrbar, minrbar := 0.0, 1e100

	info := &LeastSquaresInfo{}
	criterion := ""
	exhausted := false
	steps := 0
	uBuf := make([]float64, m)
	vBuf := make([]float64, n)
	// The estimate buffers are sized as SpLSQR's, for the same reason.
	estCap := min(maxIter, 2*n)
	rEsts := make([]float64, 0, estCap)
	arEsts := make([]float64, 0, estCap)
	normA := math.Sqrt(normA2)
	condA := 1.0
	normr := bNorm
	hScale := max(alpha, bNorm)
	// The rotation's cosine and sine live across the loop body; ρ
	// itself carries across iterations, which is what rhoold reads.
	var c, s float64

	// hitBudget tells the three exits apart, exactly as SpLSQR's: a
	// loop that ended by its own iteration count fired no criterion
	// and broke down nowhere, which is the budget's fault.
	hitBudget := true
	for itn := 1; itn <= maxIter; itn++ {
		// βu = A·v − αu, αv = Aᵀu − βv.
		op.matVec(v, uBuf)
		for i := range m {
			uBuf[i] -= alpha * u[i]
		}
		if !vecFinite(uBuf) {
			return nil, nil, base.Errf("%s: non-finite residual direction at step %d", name, itn)
		}
		beta := norm2F64(uBuf)
		hScale = max(hScale, beta)
		floor := spLeastSquaresBreakdown * base.EpsF * hScale
		if beta <= floor {
			beta = 0
			exhausted = true
		} else {
			scale = 1 / beta
			for i := range m {
				u[i] = uBuf[i] * scale
			}
			op.tMatVec(u, vBuf)
			for j := range n {
				vBuf[j] -= beta * v[j]
			}
			if !vecFinite(vBuf) {
				return nil, nil, base.Errf("%s: non-finite normal direction at step %d", name, itn)
			}
			alpha = norm2F64(vBuf)
			hScale = max(hScale, alpha)
			if alpha <= floor {
				// The v-direction is gone: α is treated as the exact
				// zero the recursion would have produced, v as the zero
				// vector, and the iteration stops after this fold.
				alpha = 0
				exhausted = true
				clear(v)
			} else if alpha > 0 {
				scale = 1 / alpha
				for j := range n {
					v[j] = vBuf[j] * scale
				}
			}
		}
		// First rotation pair: the damping fold first, as the reference
		// applies it: (ᾱ, 0) gives the sign chat and the magnitude α̂,
		// then (α̂, β) turns to ρ. c and s live in the loop, but ρ is
		// declared outside it and carries: rhoold needs the previous
		// step's value, and a `:=` here would shadow it.
		chat := sign(alphabar)
		rhoold := rho
		c, s, rho = symOrtho(math.Abs(alphabar), beta)
		if rho == 0 {
			exhausted = true
			hitBudget = false
			break
		}
		thetanew := s * alpha
		alphabar = c * alpha
		// Second rotation pair: (c̄ρ, θ) to ρ̄, which moves the
		// normal-equations estimate ζ̄.
		rhobarold := rhobar
		zetaold := zeta
		thetabar := sbar * rho
		rhotemp := cbar * rho
		cbar, sbar, rhobar = symOrtho(cbar*rho, thetanew)
		zeta = cbar * zetabar
		zetabar = -sbar * zetabar

		// The direction recurrences and the answer update.
		coef := thetabar * rho / (rhoold * rhobarold)
		for j := range n {
			hbar[j] = h[j] - coef*hbar[j]
		}
		xk := zeta / (rho * rhobar)
		for j := range n {
			x[j] += xk * hbar[j]
		}
		ht := -thetanew / rho
		for j := range n {
			h[j] = v[j] + ht*h[j]
		}
		steps = itn

		// The exact-form residual estimate: the pending right-hand side
		// entries ride the rotations, chat carrying the sign the
		// damping fold produced.
		betaacute := chat * betadd
		betahat := c * betaacute
		betadd = -s * betaacute
		thetatildeold := thetatilde
		ctildeold, stildeold, rhotildeold := symOrtho(rhodold, thetabar)
		thetatilde = stildeold * rhobar
		rhodold = ctildeold * rhobar
		betad = -stildeold*betad + ctildeold*betahat
		tautildeold = (zetaold - thetatildeold*tautildeold) / rhotildeold
		taud := (zeta - thetatilde*tautildeold) / rhodold
		normr = math.Sqrt((betad-taud)*(betad-taud) + betadd*betadd)

		// The ‖A‖ and cond(A) estimates.
		normA2 += beta * beta
		normA = math.Sqrt(normA2)
		normA2 += alpha * alpha
		maxrbar = max(maxrbar, rhobarold)
		if itn > 1 {
			minrbar = min(minrbar, rhobarold)
		}
		condA = math.Inf(1)
		if d := min(minrbar, rhotemp); d > 0 {
			condA = max(maxrbar, rhotemp) / d
		}

		normar := math.Abs(zetabar)
		normx := norm2F64(x)
		rEsts = append(rEsts, normr)
		arEsts = append(arEsts, normar)
		test1 := normr / bNorm
		test2 := math.Inf(1)
		if p := normA * normr; p != 0 {
			test2 = normar / p
		}
		test3 := 1 / (condA + base.EpsF)
		target := tol * (1 + normA*normx/bNorm)
		switch {
		case test1 <= target:
			criterion = LeastSquaresResidual
		case test2 <= tol:
			criterion = LeastSquaresNormal
		case test3 <= ctol:
			criterion = LeastSquaresCondition
		}
		if criterion != "" || exhausted {
			hitBudget = false
			break
		}
	}

	rNorm, arNorm := lsqrExplicitNorms(op, bv, x, uBuf, vBuf)
	criterion = settleLeastSquares(criterion, exhausted, rNorm, arNorm, x, bNorm, normA, tol)
	if criterion == "" {
		if exhausted {
			return nil, nil, base.Errf("%s: no convergence: the recursion folded at step %d, residual %.3g (tolerance %.3g)",
				name, steps, rNorm, tol)
		}
		if hitBudget {
			return nil, nil, base.Errf("%s: no convergence in %d steps, residual %.3g (tolerance %.3g)",
				name, maxIter, rNorm, tol)
		}
		return nil, nil, base.Errf("%s: a stopping criterion fired at step %d but its estimate drifted past the recomputed norms (residual %.3g, tolerance %.3g)",
			name, steps, rNorm, tol)
	}
	info.Iterations = steps
	info.Criterion = criterion
	info.Converged = criterion != LeastSquaresCondition
	info.ResidualNorm = rNorm
	info.NormalResidual = arNorm
	info.MatrixNorm = normA
	info.Condition = condA
	info.residualEstimates = rEsts
	info.normalEstimates = arEsts
	return floatsToArray(x, []int{n}), info, nil
}

// finishLeastSquares recomputes the explicit norms of a candidate x
// and hands the verdict to settleLeastSquares, the entry for a caller
// that holds only the operator and the vectors. The solvers call
// settleLeastSquares directly with the norms they already hold, so a
// solve never runs those two products twice.
func finishLeastSquares(name string, criterion string, exhausted bool, steps int, op *lsqrOperator, bv, x []float64, bNorm, matrixNorm, tol float64) string {
	ax := make([]float64, op.m)
	ar := make([]float64, op.n)
	rNorm, arNorm := lsqrExplicitNorms(op, bv, x, ax, ar)
	return settleLeastSquares(criterion, exhausted, rNorm, arNorm, x, bNorm, matrixNorm, tol)
}

// settleLeastSquares settles the criterion against the truth. A fired
// criterion is verified against the explicitly recomputed residual,
// with the round-off slack, so a drifted estimate cannot dress a
// broken answer up as converged; a collapse that fired no test is
// judged by its explicit norms the same way. It returns the criterion
// to report, or the empty string when the honest answer is an error.
func settleLeastSquares(criterion string, exhausted bool, rNorm, arNorm float64, x []float64, bNorm, matrixNorm, tol float64) string {
	if criterion == "" && exhausted {
		// The recursion clamped to a stop without a test firing: judge
		// the folded answer by its explicit norms.
		criterion = LeastSquaresResidual
	}
	if criterion == "" {
		return ""
	}
	final, ok := verifyLeastSquares(criterion, rNorm, arNorm, bNorm, matrixNorm, norm2F64(x), tol)
	if !ok {
		return ""
	}
	return final
}