Specialize Diagonal products and dot for adjoint/transpose of sparse matrices - #770

…rse matrices

Fixes #619: `A' * D` and `D * A'` for a sparse `A` and `Diagonal` `D` fell
through to the generic `AbstractMatrix` product, ~300x slower than `A * D`
on Julia 1.11. Materialize the adjoint (O(nnz)) and reuse the existing
CSC-times-Diagonal kernels, mirroring how `A' * B` is handled for sparse `B`.

Fixes #627: `dot(A', B)` for sparse `A`, `B` walked the stored entries of `B`
and did a binary search into `A'` for each, ~50x slower than `dot(copy(A'), B)`
on Julia 1.11. Add a merge that walks the columns of `B` in order while
keeping one cursor per column of `parent(A)`, so it runs in
O(nnz(A) + nnz(B) + n) time with O(n) extra memory and no O(nnz) temporary.
`dot(B, A')` reaches the same kernel through the existing `conj(dot(A', B))`.

Tests cover both wrappers, real and complex eltypes, mixed eltypes, stored
zeros, empty columns, non-square shapes, dimension errors, and timing guards.

Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01LgBHUw9Hp7YW5ub29B4R5y

Main split the `dot` tests out of test/linalg.jl into test/linalg_products.jl,
so the new adjoint/transpose `dot` tests move there; the `Diagonal` product
tests stay in test/linalg.jl.

Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01V6EdE4F3CCGE3vxr8gQYKf

…iagonal`

The `*` overloads only patched the symptom: LinearAlgebra's `Diagonal`
kernel visits every element of the destination, so `mul!(C, S', D)` and
the 5-argument forms stayed O(m*n). Replace the overloads with 5-argument
`mul!` methods that form the adjoint directly in `C` with one `halfperm!`
and scale it in place, falling back to a materialized copy when `beta` is
nonzero or when `C` aliases the parent, is fixed, or has another index
type. `*` reaches these through `matop_dest`, which now hands the adjoint
of a sparse matrix an empty writable destination and a fixed sparse matrix
a fixed destination with its own structure, so `D * F` and `D * F'` for a
fixed `F` no longer fail writing read-only indices.

`dot(A', B)` now walks the sparser operand and keeps cursors over the
columns of the other, so it is no longer 6-30x slower than `dot(copy(A'),
B)` when `B` is much denser than `parent(A)`; it returns early when either
operand has no stored entries and uses a binary search per entry instead
of the cursor array when the columns outnumber the stored entries, so a
huge nearly empty operand no longer costs O(n) time and memory.

Tests: the wall-clock guards are replaced by a multiplication-counting
eltype (as in #781): the kernels perform exactly `nnz` multiplications, and
`dot` only multiplies where both operands store an entry, from either side
of the walk. Two `dot` assertions that exercised the pre-existing dense
wrapper path are dropped. Fixed operands, the 3- and 5-argument `mul!`
forms, an aliased or differently indexed destination, and the no-cursor
path are covered.

Measured on nightly, min of 7: `mul!(C, S', D)` 220 ms -> 75 µs at
n=4000, 1.8 s -> 370 µs and 3.3 s -> 2.6 ms at n=10^4; `*` unchanged;
`dot(P', B)` with nnz(P)=2e3 and nnz(B)=1e7: 17.9 ms -> 0.38 ms; with two
nearly empty 10^7-row operands: 1.5 ms / 78 MiB -> 0 / 0.

Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01V6EdE4F3CCGE3vxr8gQYKf

…ias check by storage

The cursor walk in `dot(A', B)` visits every stored entry of the operand it
keeps cursors over, so it lost to the previous binary search once that operand
was much denser: `dot(Bd', P)` with nnz(P)=2e3 and nnz(Bd)=5e5 took 138 µs
against 26 µs on main. Switch to a binary search per entry when the other
operand holds over 32x more entries or columns (measured crossover 20-50x);
`dot(P', Bd)` drops from 139 µs to 24 µs and `dot(Bd', P)` is back at 26 µs.

`_adjtrans_direct` compared the destination with the parent by identity, so a
destination built on the parent's `nonzeros` array was transposed in place and
came out wrong, where the existing CSC kernel handles it. Use `Base.mightalias`.

Share the entry functions of `copy(::Adjoint)`/`copy(::Transpose)` with the
`mul!` kernels instead of repeating the lambdas.

Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015VF52nADauBDqAQaUHjoNV