NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
blas.hpp
Go to the documentation of this file.
1
14#ifndef NUMERICAL_BLAS_HPP
15#define NUMERICAL_BLAS_HPP
16
17#include <algorithm>
18#include <array>
19#include <atomic>
20#include <cmath>
21#include <complex>
22#include <cstddef>
23#include <cstdint>
24#include <cstring>
25#include <limits>
26#include <optional>
27#include <utility>
28#include <vector>
29
30#include "decomposition.hpp"
31#include "eigen.hpp"
32#include "gemm.hpp"
33#include "matrix.hpp"
34#include "parallel.hpp"
35
36namespace numerical::blas {
37
40 inline constexpr double lapack_precision {0x1p-53};
41
44 inline constexpr std::size_t syrk_block {128};
45
47 inline constexpr std::size_t syrk_kept_limit {(std::size_t {32} << 20U) / sizeof(double)};
48
49 namespace detail {
50
53 {
54 thread_local buffer<double> storage;
55 [[maybe_unused]] thread_local const bool registered {numerical::detail::on_release([] { storage = buffer<double> {}; })};
56 return storage;
57 }
58
60 [[nodiscard]] constexpr bool is_operation(char op) noexcept
61 {
62 return op == 'N' || op == 'n' || op == 'T' || op == 't' || op == 'C' || op == 'c';
63 }
64
66 [[nodiscard]] constexpr bool transposes(char op) noexcept
67 {
68 return op != 'N' && op != 'n';
69 }
70
72 [[nodiscard]] constexpr bool conjugates(char op) noexcept
73 {
74 return op == 'C' || op == 'c';
75 }
76
78 template <typename T>
79 [[nodiscard]] bool finite(const T& x)
80 {
81 return std::isfinite(x);
82 }
83
85 template <typename U>
86 [[nodiscard]] bool finite(const std::complex<U>& x)
87 {
88 return std::isfinite(x.real()) && std::isfinite(x.imag());
89 }
90
94 inline constexpr std::size_t transpose_tile {32};
95
100 inline constexpr std::size_t transpose_weight {4};
101
104 template <typename T>
106 const T* a,
107 std::ptrdiff_t lda,
108 std::ptrdiff_t rows,
109 std::ptrdiff_t cols,
110 T scale,
111 bool conjugate = false)
112 {
113 const auto r {static_cast<std::size_t>(rows)};
114 const auto c {static_cast<std::size_t>(cols)};
115 const auto ld {static_cast<std::size_t>(lda)};
116 out.resize(r * c);
117 T* const to {out.data()};
118 const std::size_t piece {numerical::detail::transpose_piece(ld * sizeof(T), c * sizeof(T))};
120 const std::size_t i0 {band * transpose_tile};
121 for (std::size_t j0 {0}; j0 < c; j0 += transpose_tile) {
123 [a, ld, c, to, scale, conjugate](std::size_t j, std::size_t i) {
124 const T x {a[i + (j * ld)]};
125 to[(i * c) + j] = scale * (conjugate ? numerical::detail::conj_of(x) : x);
126 });
127 }
128 });
129 }
130
133 template <typename T>
135 std::ptrdiff_t lda,
136 std::ptrdiff_t rows,
137 std::ptrdiff_t cols,
138 T scale,
139 bool conjugate = false)
140 {
141 buffer<T> out;
142 row_major_into(out, a, lda, rows, cols, scale, conjugate);
143 return out;
144 }
145
147 inline constexpr std::size_t kept_bytes {std::size_t {32} << 20U};
148
154 template <typename T>
155 [[nodiscard]] buffer<T>& kept_storage(std::size_t slot) noexcept
156 {
157 thread_local std::array<buffer<T>, 2> kept;
158 [[maybe_unused]] thread_local const bool registered {numerical::detail::on_release([] { kept = std::array<buffer<T>, 2> {}; })};
159 return kept[slot];
160 }
161
163 template <typename T>
165 {
166 return std::exchange(kept_storage<T>(slot), buffer<T> {});
167 }
168
170 template <typename T>
171 void give_back(std::size_t slot,
173 {
174 if (storage.capacity() <= kept_bytes / sizeof(T)) {
175 kept_storage<T>(slot) = std::move(storage);
176 }
177 }
178
185 template <typename T>
186 [[nodiscard]] bool is_identity(const T* b,
187 std::size_t ldb,
188 std::size_t n)
189 {
190 buffer<T> unit((2 * n) - 1, T {});
191 unit[n - 1] = T {1};
192 const T* const middle {unit.data() + (n - 1)};
193 if (std::memcmp(b, middle, n * sizeof(T)) != 0) {
194 return false;
195 }
196 std::atomic<bool> holds {true};
197 numerical::detail::parallel_for(n - 1, transpose_weight * n, [b, ldb, n, middle, &holds](std::size_t j) {
198 if (std::memcmp(b + ((j + 1) * ldb), middle - (j + 1), n * sizeof(T)) != 0) {
199 holds.store(false, std::memory_order_relaxed);
200 }
201 });
202 return holds.load(std::memory_order_relaxed);
203 }
204
206 template <typename T>
208 std::size_t rows,
209 std::size_t cols,
210 T* a,
211 std::size_t lda)
212 {
213 const std::size_t piece {numerical::detail::transpose_piece(cols * sizeof(T), lda * sizeof(T))};
214 numerical::detail::parallel_for((cols + transpose_tile - 1) / transpose_tile, transpose_weight * transpose_tile * rows, [from, rows, cols, a, lda, piece](std::size_t band) {
215 const std::size_t j0 {band * transpose_tile};
216 for (std::size_t i0 {0}; i0 < rows; i0 += transpose_tile) {
217 numerical::detail::transpose_walk(i0, std::min(i0 + transpose_tile, rows), j0, std::min(j0 + transpose_tile, cols), piece,
218 [from, cols, a, lda](std::size_t i, std::size_t j) { a[i + (j * lda)] = from[(i * cols) + j]; });
219 }
220 });
221 }
222
224 template <typename T>
226 std::size_t n,
227 const std::size_t* to,
228 T* a,
229 std::size_t lda)
230 {
231 const std::size_t piece {numerical::detail::transpose_piece(n * sizeof(T), lda * sizeof(T))};
233 const std::size_t j0 {band * transpose_tile};
234 for (std::size_t i0 {0}; i0 < n; i0 += transpose_tile) {
236 [from, n, to, a, lda](std::size_t i, std::size_t j) { a[i + (to[j] * lda)] = from[(i * n) + j]; });
237 }
238 });
239 }
240
246 template <typename T>
248 std::size_t m,
249 std::size_t n,
250 std::size_t k,
251 const T* l,
252 std::size_t ldl,
253 const T* a,
254 std::size_t lda,
255 T* c,
256 std::size_t ldc)
257 {
258 const bool copied {transposes(transa)};
259 const buffer<T> right {copied ? row_major(a, static_cast<std::ptrdiff_t>(lda), static_cast<std::ptrdiff_t>(k), static_cast<std::ptrdiff_t>(n), T {1}, conjugates(transa))
260 : buffer<T> {}};
261 numerical::detail::gemm(m, n, k, l, ldl, copied ? right.data() : a, copied ? n : lda, c, ldc);
262 }
263
266 inline void product_by_op_a(char transa,
267 std::size_t m,
268 std::size_t n,
269 std::size_t k,
270 const double* l,
271 std::size_t ldl,
272 const double* a,
273 std::size_t lda,
274 double* c,
275 std::size_t ldc)
276 {
277 if (transposes(transa)) {
278 numerical::detail::gemm_bt(m, n, k, l, ldl, a, lda, c, ldc);
279 return;
280 }
281 numerical::detail::gemm(m, n, k, l, ldl, a, lda, c, ldc);
282 }
283
287 template <typename T>
289 std::size_t lda,
290 std::size_t n,
291 T* rows,
292 bool in)
293 {
294 const std::size_t piece {numerical::detail::transpose_piece(lda * sizeof(T), n * sizeof(T))};
295 numerical::detail::parallel_for((n + transpose_tile - 1) / transpose_tile, transpose_weight * transpose_tile * n / 2, [a, lda, n, rows, in, piece](std::size_t band) {
296 const std::size_t i0 {band * transpose_tile};
297 for (std::size_t j0 {0}; j0 <= i0; j0 += transpose_tile) {
299 [a, lda, n, rows, in](std::size_t j, std::size_t i) {
300 if (i < j) { // the upper triangle, untouched
301 return;
302 }
303 if (in) {
304 rows[(i * n) + j] = a[i + (j * lda)];
305 }
306 else {
307 a[i + (j * lda)] = rows[(i * n) + j];
308 }
309 });
310 }
311 });
312 }
313
316 template <typename T>
318 std::ptrdiff_t lda,
319 std::ptrdiff_t rows,
320 std::ptrdiff_t cols,
321 T scale)
322 {
323 const auto r {static_cast<std::size_t>(rows)};
324 const auto c {static_cast<std::size_t>(cols)};
325 buffer<T> out(r * c);
326 for (std::size_t j {0}; j < c; ++j) {
327 for (std::size_t i {0}; i < r; ++i) {
328 out[(j * r) + i] = scale * a[i + (j * static_cast<std::size_t>(lda))];
329 }
330 }
331 return out;
332 }
333
340 template <typename T>
342 char transb,
343 T alpha,
344 std::size_t m,
345 std::size_t n,
346 std::size_t k,
347 const T* a,
348 std::size_t lda,
349 const T* b,
350 std::size_t ldb,
351 T* c,
352 std::size_t ldc)
353 {
354 const bool copy_b {transposes(transb) || alpha != T {1}};
355 buffer<T> left {};
356 if (transposes(transb)) {
357 left = row_major(b, static_cast<std::ptrdiff_t>(ldb), static_cast<std::ptrdiff_t>(m), static_cast<std::ptrdiff_t>(k), alpha,
359 }
360 else if (copy_b) {
361 left = columns_as_rows(b, static_cast<std::ptrdiff_t>(ldb), static_cast<std::ptrdiff_t>(k), static_cast<std::ptrdiff_t>(m), alpha);
362 }
363 product_by_op_a(transa, m, n, k, copy_b ? left.data() : b, copy_b ? k : ldb, a, lda, c, ldc);
364 }
365
369 inline void product_of_ops(char transa,
370 char transb,
371 double alpha,
372 std::size_t m,
373 std::size_t n,
374 std::size_t k,
375 const double* a,
376 std::size_t lda,
377 const double* b,
378 std::size_t ldb,
379 double* c,
380 std::size_t ldc)
381 {
382 if (!transposes(transb) || alpha != 1.0) {
383 product_of_ops<double>(transa, transb, alpha, m, n, k, a, lda, b, ldb, c, ldc);
384 return;
385 }
386 if (transposes(transa)) {
387 numerical::detail::gemm_atbt(m, n, k, b, ldb, a, lda, c, ldc);
388 return;
389 }
390 numerical::detail::gemm_at(m, n, k, b, ldb, a, lda, c, ldc);
391 }
392 } // namespace detail
393
394 namespace detail {
395
398 template <typename Index>
399 void interchanges(const std::vector<std::size_t>& pivots,
400 Index* ipiv)
401 {
402 const std::size_t size {pivots.size()};
403 std::vector<std::size_t> at(size); // the original row at each position
404 std::vector<std::size_t> where(size); // the position of each original row
405 for (std::size_t i {0}; i < size; ++i) {
406 at[i] = i;
407 where[i] = i;
408 }
409 for (std::size_t i {0}; i < size; ++i) {
410 const std::size_t from {where[pivots[i]]};
411 ipiv[i] = static_cast<Index>(from + 1);
412 where[at[i]] = from;
413 where[pivots[i]] = i;
414 std::swap(at[i], at[from]);
415 }
416 }
417
422 template <typename T, typename Index>
423 int rectangular_lu(std::size_t m,
424 std::size_t n,
425 T* a,
426 std::size_t lda,
427 Index* ipiv)
428 {
429 int info {0};
430 for (std::size_t j {0}; j < std::min(m, n); ++j) {
431 T* const column {a + (j * lda)};
432 std::size_t pivot {j};
433 for (std::size_t i {j + 1}; i < m; ++i) {
434 if (numerical::detail::pivot_magnitude(column[i]) > numerical::detail::pivot_magnitude(column[pivot])) { // izamax's |Re| + |Im| of a complex one
435 pivot = i;
436 }
437 }
438 ipiv[j] = static_cast<Index>(pivot + 1);
439 if (column[pivot] == T {}) {
440 info = info == 0 ? static_cast<int>(j + 1) : info;
441 continue;
442 }
443 for (std::size_t c {0}; c < n; ++c) { // the whole rows interchanged, as dgetf2's dswap
444 std::swap(a[j + (c * lda)], a[pivot + (c * lda)]);
445 }
446 for (std::size_t i {j + 1}; i < m; ++i) {
447 column[i] = column[i] / column[j];
448 }
449 for (std::size_t c {j + 1}; c < n; ++c) {
450 T* const target {a + (c * lda)};
451 const T factor {target[j]};
452 for (std::size_t i {j + 1}; i < m; ++i) {
453 target[i] -= column[i] * factor;
454 }
455 }
456 }
457 return info;
458 }
459 } // namespace detail
460
468 template <typename T>
469 int gemm(char transa,
470 char transb,
471 std::ptrdiff_t m,
472 std::ptrdiff_t n,
473 std::ptrdiff_t k,
474 T alpha,
475 const T* a,
476 std::ptrdiff_t lda,
477 const T* b,
478 std::ptrdiff_t ldb,
479 T beta,
480 T* c,
481 std::ptrdiff_t ldc)
482 {
483 const std::ptrdiff_t a_rows {detail::transposes(transa) ? k : m};
484 const std::ptrdiff_t b_rows {detail::transposes(transb) ? n : k};
485 int illegal {0};
487 illegal = 1;
488 }
489 else if (!detail::is_operation(transb)) {
490 illegal = 2;
491 }
492 else if (m < 0) {
493 illegal = 3;
494 }
495 else if (n < 0) {
496 illegal = 4;
497 }
498 else if (k < 0) {
499 illegal = 5;
500 }
501 else if (lda < std::max<std::ptrdiff_t>(1, a_rows)) {
502 illegal = 8;
503 }
504 else if (ldb < std::max<std::ptrdiff_t>(1, b_rows)) {
505 illegal = 10;
506 }
507 else if (ldc < std::max<std::ptrdiff_t>(1, m)) {
508 illegal = 13;
509 }
510 if (illegal != 0 || m == 0 || n == 0) {
511 return illegal;
512 }
513 const auto rows {static_cast<std::size_t>(m)};
514 const auto cols {static_cast<std::size_t>(n)};
515 const auto stride {static_cast<std::size_t>(ldc)};
516 for (std::size_t j {0}; j < cols; ++j) { // C ← β C, column by column
517 T* const column {c + (j * stride)};
518 if (beta == T {}) {
519 std::fill_n(column, rows, T {});
520 }
521 else if (beta != T {1}) {
522 std::transform(column, column + rows, column, [beta](T x) { return beta * x; });
523 }
524 }
525 if (alpha == T {} || k == 0) {
526 return 0;
527 }
528 detail::product_of_ops(transa, transb, alpha, cols, rows, static_cast<std::size_t>(k), a, static_cast<std::size_t>(lda), b,
529 static_cast<std::size_t>(ldb), c, stride);
530 return 0;
531 }
532
533 namespace detail {
534
537 [[nodiscard]] constexpr std::size_t strided(std::size_t i,
538 std::size_t length,
539 std::ptrdiff_t inc) noexcept
540 {
541 // The magnitude of a negative inc in unsigned arithmetic: -inc of PTRDIFF_MIN overflows.
542 return inc > 0 ? i * static_cast<std::size_t>(inc) : (length - 1 - i) * (std::size_t {0} - static_cast<std::size_t>(inc));
543 }
544
546 template <typename T>
547 [[nodiscard]] T real_dot(std::ptrdiff_t n,
548 const T* x,
549 std::ptrdiff_t incx,
550 const T* y,
551 std::ptrdiff_t incy)
552 {
553 if (n <= 0) {
554 return T {};
555 }
556 const auto count {static_cast<std::size_t>(n)};
557 if (incx == 1 && incy == 1) {
558 return numerical::detail::chunked_dot(x, y, count);
559 }
560 buffer<T> xs(count, T {});
561 buffer<T> ys(count, T {});
562 for (std::size_t i {0}; i < count; ++i) {
563 xs[i] = x[strided(i, count, incx)];
564 ys[i] = y[strided(i, count, incy)];
565 }
566 return numerical::detail::chunked_dot(xs.data(), ys.data(), count);
567 }
568 } // namespace detail
569
575 [[nodiscard]] inline double dot(std::ptrdiff_t n,
576 const double* x,
577 std::ptrdiff_t incx,
578 const double* y,
579 std::ptrdiff_t incy)
580 {
581 return detail::real_dot(n, x, incx, y, incy);
582 }
583
585 [[nodiscard]] inline float dot(std::ptrdiff_t n,
586 const float* x,
587 std::ptrdiff_t incx,
588 const float* y,
589 std::ptrdiff_t incy)
590 {
591 return detail::real_dot(n, x, incx, y, incy);
592 }
593
601 template <typename T>
602 [[nodiscard]] std::complex<T> complex_dot(bool conjugate,
603 std::ptrdiff_t n,
604 const std::complex<T>* x,
605 std::ptrdiff_t incx,
606 const std::complex<T>* y,
607 std::ptrdiff_t incy) noexcept
608 {
609 std::complex<T> sum {};
610 if (n <= 0) {
611 return sum;
612 }
613 const auto count {static_cast<std::size_t>(n)};
614 if (incx == 1 && incy == 1) {
616 }
617 for (std::size_t i {0}; i < count; ++i) {
618 const std::complex<T> xi {x[detail::strided(i, count, incx)]};
619 sum += (conjugate ? std::conj(xi) : xi) * y[detail::strided(i, count, incy)];
620 }
621 return sum;
622 }
623
626 inline constexpr std::size_t gemv_rows {64};
627
631 inline constexpr std::size_t gemv_weight {4};
632
640 inline int gemv(char trans,
641 std::ptrdiff_t m,
642 std::ptrdiff_t n,
643 double alpha,
644 const double* a,
645 std::ptrdiff_t lda,
646 const double* x,
647 std::ptrdiff_t incx,
648 double beta,
649 double* y,
650 std::ptrdiff_t incy)
651 {
653 return 1;
654 }
655 if (m < 0) {
656 return 2;
657 }
658 if (n < 0) {
659 return 3;
660 }
661 if (lda < std::max<std::ptrdiff_t>(1, m)) {
662 return 6;
663 }
664 if (incx == 0) {
665 return 8;
666 }
667 if (incy == 0) {
668 return 11;
669 }
670 if (m == 0 || n == 0 || (alpha == 0.0 && beta == 1.0)) {
671 return 0;
672 }
673 const bool transposed {detail::transposes(trans)};
674 const auto rows {static_cast<std::size_t>(m)};
675 const auto cols {static_cast<std::size_t>(n)};
676 const auto ld {static_cast<std::size_t>(lda)};
677 const std::size_t x_length {transposed ? rows : cols};
678 const std::size_t y_length {transposed ? cols : rows};
679 // y itself where its elements are contiguous, else a copy written back; x itself for Aᵀ x where it is contiguous
680 // and α 1, else α x gathered (A x takes −α x, its factors): the same values either way, so the same bits.
682 double* const out {incy == 1 ? y : gathered_y.data()};
683 for (std::size_t i {0}; i < y_length; ++i) {
684 out[i] = beta == 0.0 ? 0.0 : beta * y[detail::strided(i, y_length, incy)];
685 }
686 if (alpha != 0.0) {
687 const bool in_place {transposed && incx == 1 && alpha == 1.0};
688 buffer<double> scaled(in_place ? 0 : x_length); // α x, gathered
689 for (std::size_t i {0}; i < scaled.size(); ++i) {
690 scaled[i] = alpha * x[detail::strided(i, x_length, incx)];
691 }
692 if (transposed) {
693 const double* const factors {in_place ? x : scaled.data()};
694 buffer<double> dots(cols, 0.0);
695 numerical::detail::parallel_for((cols + gemv_rows - 1) / gemv_rows, gemv_weight * gemv_rows * rows, [&](std::size_t group) {
696 const std::size_t first {group * gemv_rows};
697 numerical::detail::row_dots(a + (first * ld), ld, std::min(gemv_rows, cols - first),
698 factors, rows, dots.data() + first);
699 });
700 for (std::size_t j {0}; j < cols; ++j) {
701 out[j] += dots[j];
702 }
703 }
704 else { // A x: each task's rows of y held through every column (numerical::detail::subtract_products, the
705 // factors −α x_j), each element fma(α x_j, a_ij, y_i) for j ascending, as column by column
706 for (double& factor : scaled) {
707 factor = -factor;
708 }
709 numerical::detail::parallel_for((rows + gemv_rows - 1) / gemv_rows, gemv_weight * gemv_rows * cols, [&](std::size_t group) {
710 const std::size_t first {group * gemv_rows};
711 numerical::detail::subtract_products(out + first, scaled.data(), a + first, ld, cols,
712 std::min(gemv_rows, rows - first));
713 });
714 }
715 }
716 for (std::size_t i {0}; incy != 1 && i < y_length; ++i) {
717 y[detail::strided(i, y_length, incy)] = out[i];
718 }
719 return 0;
720 }
721
722 namespace detail {
723
727 {
728 const double* p;
729 std::size_t ldp;
730 const double* q;
731 std::size_t ldq;
732 std::size_t depth;
733 double* c;
734 std::size_t ldc;
735 bool lower;
736 bool q_is_pt;
737 bool p_is_qt;
738 };
739
744 std::size_t c0,
745 std::size_t cols,
746 std::size_t r0,
747 std::size_t rows,
748 double* out,
749 std::size_t ldo)
750 {
751 if (operands.q_is_pt) {
752 numerical::detail::gemm_bt(cols, rows, operands.depth, operands.p + (c0 * operands.ldp), operands.ldp, operands.p + (r0 * operands.ldp),
753 operands.ldp, out, ldo);
754 return;
755 }
756 if (operands.p_is_qt) {
757 numerical::detail::gemm_at(cols, rows, operands.depth, operands.q + c0, operands.ldq, operands.q + r0, operands.ldq, out, ldo);
758 return;
759 }
760 numerical::detail::gemm(cols, rows, operands.depth, operands.p + (c0 * operands.ldp), operands.ldp, operands.q + r0, operands.ldq, out, ldo);
761 }
762
770 std::size_t j0,
771 std::size_t w)
772 {
773 if (w <= syrk_block) {
774 buffer<double> diagonal(w * w, 0.0); // row-major: (i, j) is C(j0 + j, j0 + i)
775 syrk_product(operands, j0, w, j0, w, diagonal.data(), w);
776 for (std::size_t j {0}; j < w; ++j) {
777 for (std::size_t i {operands.lower ? j : 0}; i < (operands.lower ? w : j + 1); ++i) {
778 operands.c[(j0 + i) + ((j0 + j) * operands.ldc)] += diagonal[(j * w) + i];
779 }
780 }
781 return;
782 }
783 const std::size_t h {w / 2};
785 const std::size_t r0 {operands.lower ? j0 + h : j0}; // below the first half (L), or right of it (U)
786 const std::size_t c0 {operands.lower ? j0 : j0 + h};
787 const std::size_t rows {operands.lower ? w - h : h};
788 const std::size_t cols {operands.lower ? h : w - h};
789 syrk_product(operands, c0, cols, r0, rows, operands.c + r0 + (c0 * operands.ldc), operands.ldc);
790 syrk_triangle(operands, j0 + h, w - h);
791 }
792
799 inline void syrk_all(const syrk_operands& operands,
800 std::size_t n)
801 {
802 const std::size_t k {operands.depth};
804 syrk_triangle(operands, 0, n);
805 return;
806 }
807 const bool m_lower {!operands.lower};
808 if (operands.q_is_pt) {
810 n, k, operands.p, operands.ldp, operands.p, operands.ldp, operands.c, operands.ldc, m_lower);
811 return;
812 }
813 if (operands.p_is_qt) {
815 n, k, operands.q, operands.ldq, operands.q, operands.ldq, operands.c, operands.ldc, m_lower);
816 return;
817 }
819 n, k, operands.p, operands.ldp, operands.q, operands.ldq, operands.c, operands.ldc, m_lower);
820 }
821 } // namespace detail
822
830 inline int syrk(char uplo,
831 char trans,
832 std::ptrdiff_t n,
833 std::ptrdiff_t k,
834 double alpha,
835 const double* a,
836 std::ptrdiff_t lda,
837 double beta,
838 double* c,
839 std::ptrdiff_t ldc)
840 {
841 const bool lower {uplo == 'L' || uplo == 'l'};
842 const bool transposed {detail::transposes(trans)};
843 if (!lower && uplo != 'U' && uplo != 'u') {
844 return 1;
845 }
847 return 2;
848 }
849 if (n < 0) {
850 return 3;
851 }
852 if (k < 0) {
853 return 4;
854 }
855 if (lda < std::max<std::ptrdiff_t>(1, transposed ? k : n)) {
856 return 7;
857 }
858 if (ldc < std::max<std::ptrdiff_t>(1, n)) {
859 return 10;
860 }
861 if (n == 0) {
862 return 0;
863 }
864 const auto order {static_cast<std::size_t>(n)};
865 const auto ld {static_cast<std::size_t>(ldc)};
866 if (alpha == 0.0 || k == 0) { // C ← β C on the triangle
867 for (std::size_t j {0}; j < order && beta != 1.0; ++j) {
868 for (std::size_t i {lower ? j : 0}; i < (lower ? order : j + 1); ++i) {
869 c[i + (j * ld)] = beta == 0.0 ? 0.0 : beta * c[i + (j * ld)];
870 }
871 }
872 return 0;
873 }
874 // C(r, c) = α Σ_l op(A)(r, l) op(A)(c, l). The kernel takes row-major operands: P = op(A) (n × k) and
875 // Q = op(A)ᵀ (k × n). A column-major A is one of them read in place (Q for N, P for T). With α = 1 the other is
876 // read from it as its transpose (detail::syrk_product; NumPy's a @ a.T is T): no copy, the same bits. Otherwise
877 // the other is copied once, α folded into it.
878 const auto depth {static_cast<std::size_t>(k)};
879 const auto lda_s {static_cast<std::size_t>(lda)};
880 for (std::size_t j {0}; j < order; ++j) { // C ← β C on the triangle; the products then add into it
881 for (std::size_t i {lower ? j : 0}; i < (lower ? order : j + 1); ++i) {
882 double& entry {c[i + (j * ld)]};
883 entry = beta == 0.0 ? 0.0 : beta * entry;
884 }
885 }
886 if (alpha == 1.0) {
887 detail::syrk_all({transposed ? a : nullptr, lda_s, transposed ? nullptr : a, lda_s, depth, c, ld, lower, transposed, !transposed}, order);
888 return 0;
889 }
890 // The copy in storage the thread keeps between calls (as the kernel's packing_storage): a fresh one of a megabyte
891 // is mapped anew and faulted in page by page on every call.
893 const std::size_t copy_rows {transposed ? depth : order}; // row-major: α A as it lies, k × n (T) or n × k (N)
894 const std::size_t copy_cols {transposed ? order : depth};
895 if (copy.size() < copy_rows * copy_cols) {
897 }
898 for (std::size_t i {0}; i < copy_rows; ++i) {
899 for (std::size_t j {0}; j < copy_cols; ++j) {
900 copy[(i * copy_cols) + j] = alpha * a[i + (j * lda_s)];
901 }
902 }
903 const double* const p_rows {transposed ? a : copy.data()};
904 const std::size_t ldp {transposed ? lda_s : depth};
905 const double* const q_cols {transposed ? copy.data() : a};
906 const std::size_t ldq {transposed ? order : lda_s};
907 detail::syrk_all({p_rows, ldp, q_cols, ldq, depth, c, ld, lower, false, false}, order);
908 if (copy.size() <= syrk_kept_limit) {
909 detail::syrk_operand() = std::move(copy);
910 }
911 return 0;
912 }
913
915 inline constexpr std::size_t trsm_block {64};
916
917 namespace detail {
918
925 inline void triangular_solve(bool lower,
926 bool unit,
927 std::size_t k,
928 std::size_t n,
929 const double* a,
930 std::size_t lda,
931 double* b,
932 std::size_t ldb)
933 {
934 for (std::size_t done {0}; done < k; done += trsm_block) {
935 const std::size_t w {std::min(trsm_block, k - done)};
936 const std::size_t k0 {lower ? done : k - done - w};
937 const std::size_t k1 {k0 + w};
938 // The block's triangle, each column of B alone, the columns in parallel.
939 numerical::detail::parallel_for(n, w * w, [a, b, lda, ldb, k0, k1, lower, unit](std::size_t j) {
940 double* x {b + (j * ldb)};
941 for (std::size_t s {0}; s < k1 - k0; ++s) {
942 const std::size_t p {lower ? k0 + s : k1 - 1 - s};
943 if (!unit) {
944 x[p] /= a[p + (p * lda)];
945 }
946 const std::size_t from {lower ? p + 1 : k0};
947 const std::size_t to {lower ? k1 : p};
948 numerical::detail::add_product(x + from, -x[p], a + from + (p * lda), to - from);
949 }
950 });
951 const std::size_t first {lower ? k1 : 0};
952 const std::size_t count {lower ? k - k1 : k0};
953 if (count > 0) { // B(rows still to solve) −= A(those rows, block) X(block)
954 (void)gemm('N', 'N', static_cast<std::ptrdiff_t>(count), static_cast<std::ptrdiff_t>(n), static_cast<std::ptrdiff_t>(w), -1.0,
955 a + first + (k0 * lda), static_cast<std::ptrdiff_t>(lda), b + k0, static_cast<std::ptrdiff_t>(ldb), 1.0, b + first,
956 static_cast<std::ptrdiff_t>(ldb));
957 }
958 }
959 }
960 } // namespace detail
961
970 inline int trsm(char side,
971 char uplo,
972 char transa,
973 char diag,
974 std::ptrdiff_t m,
975 std::ptrdiff_t n,
976 double alpha,
977 const double* a,
978 std::ptrdiff_t lda,
979 double* b,
980 std::ptrdiff_t ldb)
981 {
982 const bool left {side == 'L' || side == 'l'};
983 const bool lower {uplo == 'L' || uplo == 'l'};
984 const bool unit {diag == 'U' || diag == 'u'};
985 if (!left && side != 'R' && side != 'r') {
986 return 1;
987 }
988 if (!lower && uplo != 'U' && uplo != 'u') {
989 return 2;
990 }
992 return 3;
993 }
994 if (!unit && diag != 'N' && diag != 'n') {
995 return 4;
996 }
997 if (m < 0) {
998 return 5;
999 }
1000 if (n < 0) {
1001 return 6;
1002 }
1003 if (lda < std::max<std::ptrdiff_t>(1, left ? m : n)) {
1004 return 9;
1005 }
1006 if (ldb < std::max<std::ptrdiff_t>(1, m)) {
1007 return 11;
1008 }
1009 if (m == 0 || n == 0) {
1010 return 0;
1011 }
1012 const auto rows {static_cast<std::size_t>(m)};
1013 const auto cols {static_cast<std::size_t>(n)};
1014 const auto ld {static_cast<std::size_t>(ldb)};
1015 for (std::size_t j {0}; j < cols; ++j) {
1016 for (std::size_t i {0}; i < rows; ++i) {
1017 double& entry {b[i + (j * ld)]};
1018 entry = alpha == 0.0 ? 0.0 : alpha * entry;
1019 }
1020 }
1021 if (alpha == 0.0) {
1022 return 0;
1023 }
1024 const std::size_t k {left ? rows : cols};
1025 const bool flip_a {left == detail::transposes(transa)}; // A' = Aᵀ: op(A) = Aᵀ on the left, A on the right
1027 const double* a_used {a};
1028 std::size_t lda_used {static_cast<std::size_t>(lda)};
1029 if (flip_a) {
1030 transposed_a = buffer<double>(k * k, 0.0);
1031 for (std::size_t j {0}; j < k; ++j) {
1032 for (std::size_t i {lower ? j : 0}; i < (lower ? k : j + 1); ++i) { // A's triangle, transposed
1033 transposed_a[j + (i * k)] = a[i + (j * static_cast<std::size_t>(lda))];
1034 }
1035 }
1036 a_used = transposed_a.data();
1037 lda_used = k;
1038 }
1039 if (left) {
1040 detail::triangular_solve(lower != flip_a, unit, k, cols, a_used, lda_used, b, ld);
1041 return 0;
1042 }
1043 buffer<double> bt(cols * rows, 0.0); // Bᵀ, column-major n × m
1044 for (std::size_t j {0}; j < cols; ++j) {
1045 for (std::size_t i {0}; i < rows; ++i) {
1046 bt[j + (i * cols)] = b[i + (j * ld)];
1047 }
1048 }
1049 detail::triangular_solve(lower != flip_a, unit, k, rows, a_used, lda_used, bt.data(), cols);
1050 for (std::size_t j {0}; j < cols; ++j) {
1051 for (std::size_t i {0}; i < rows; ++i) {
1052 b[i + (j * ld)] = bt[j + (i * cols)];
1053 }
1054 }
1055 return 0;
1056 }
1057
1058 namespace detail {
1064 inline constexpr std::size_t trsm_columns_least {8};
1065
1068 template <typename T, typename Index>
1070 std::size_t size,
1071 std::size_t nrhs,
1072 const T* a,
1073 std::size_t ld,
1074 const Index* ipiv,
1075 T* b,
1076 std::size_t ldb)
1077 {
1078 const bool conjugate {detail::conjugates(trans)};
1079 const auto at = [&](std::size_t i, std::size_t j) { return a[i + (j * ld)]; };
1080 // An element of op(A)'s factor read transposed: conjugated for Aᴴ.
1081 const auto across = [&](std::size_t i, std::size_t j) { return conjugate ? numerical::detail::conj_of(at(i, j)) : at(i, j); };
1082 for (std::size_t c {0}; c < nrhs; ++c) {
1083 T* const x {b + (c * ldb)};
1084 if (!detail::transposes(trans)) { // L U x = P b
1085 for (std::size_t i {0}; i < size; ++i) {
1086 std::swap(x[i], x[static_cast<std::size_t>(ipiv[i]) - 1]);
1087 }
1088 for (std::size_t j {0}; j < size; ++j) { // L, unit lower, by columns
1089 for (std::size_t i {j + 1}; i < size; ++i) {
1090 x[i] -= at(i, j) * x[j];
1091 }
1092 }
1093 for (std::size_t j {size}; j-- > 0;) { // U, by columns
1094 x[j] /= at(j, j);
1095 for (std::size_t i {0}; i < j; ++i) {
1096 x[i] -= at(i, j) * x[j];
1097 }
1098 }
1099 continue;
1100 }
1101 for (std::size_t i {0}; i < size; ++i) { // Uᵀ (Uᴴ), by rows of U's columns
1102 T sum {x[i]};
1103 for (std::size_t k {0}; k < i; ++k) {
1104 sum -= across(k, i) * x[k];
1105 }
1106 x[i] = sum / across(i, i);
1107 }
1108 for (std::size_t i {size}; i-- > 0;) { // Lᵀ (Lᴴ)
1109 T sum {x[i]};
1110 for (std::size_t k {i + 1}; k < size; ++k) {
1111 sum -= across(k, i) * x[k];
1112 }
1113 x[i] = sum;
1114 }
1115 for (std::size_t i {size}; i-- > 0;) { // Pᵀ: the interchanges undone in reverse
1116 std::swap(x[i], x[static_cast<std::size_t>(ipiv[i]) - 1]);
1117 }
1118 }
1119 }
1120
1125 template <typename Index>
1127 std::size_t size,
1128 std::size_t nrhs,
1129 const double* a,
1130 std::size_t ld,
1131 const Index* ipiv,
1132 double* b,
1133 std::size_t ldb)
1134 {
1135 if (nrhs < trsm_columns_least) { // a few columns: trsm's copy of op(A) outweighs its blocks
1136 getrs_columns<double, Index>(trans, size, nrhs, a, ld, ipiv, b, ldb);
1137 return;
1138 }
1139 const auto n {static_cast<std::ptrdiff_t>(size)};
1140 const auto columns {static_cast<std::ptrdiff_t>(nrhs)};
1141 const auto lda {static_cast<std::ptrdiff_t>(ld)};
1142 const auto ldb_ {static_cast<std::ptrdiff_t>(ldb)};
1143 const auto exchange = [&](std::size_t i) { // rows i and ipiv[i] of every column
1144 const auto other {static_cast<std::size_t>(ipiv[i]) - 1};
1145 for (std::size_t c {0}; c < nrhs; ++c) {
1146 std::swap(b[i + (c * ldb)], b[other + (c * ldb)]);
1147 }
1148 };
1149 if (!transposes(trans)) { // L U X = P B
1150 for (std::size_t i {0}; i < size; ++i) {
1151 exchange(i);
1152 }
1153 (void)trsm('L', 'L', 'N', 'U', n, columns, 1.0, a, lda, b, ldb_);
1154 (void)trsm('L', 'U', 'N', 'N', n, columns, 1.0, a, lda, b, ldb_);
1155 return;
1156 }
1157 (void)trsm('L', 'U', 'T', 'N', n, columns, 1.0, a, lda, b, ldb_); // Uᵀ, then Lᵀ: Aᵀ X = B (Aᴴ the same, real)
1158 (void)trsm('L', 'L', 'T', 'U', n, columns, 1.0, a, lda, b, ldb_);
1159 for (std::size_t i {size}; i-- > 0;) { // Pᵀ: the interchanges undone in reverse
1160 exchange(i);
1161 }
1162 }
1163 } // namespace detail
1164
1165 template <typename T, typename Index>
1166 int getrs(char trans,
1167 std::ptrdiff_t n,
1168 std::ptrdiff_t nrhs,
1169 const T* a,
1170 std::ptrdiff_t lda,
1171 const Index* ipiv,
1172 T* b,
1173 std::ptrdiff_t ldb);
1174
1185 template <typename T, typename Index>
1186 int gesv(std::ptrdiff_t n,
1187 std::ptrdiff_t nrhs,
1188 T* a,
1189 std::ptrdiff_t lda,
1190 Index* ipiv,
1191 T* b,
1192 std::ptrdiff_t ldb)
1193 {
1194 if (n < 0) {
1195 return -1;
1196 }
1197 if (nrhs < 0) {
1198 return -2;
1199 }
1200 if (lda < std::max<std::ptrdiff_t>(1, n)) {
1201 return -4;
1202 }
1203 if (ldb < std::max<std::ptrdiff_t>(1, n)) {
1204 return -7;
1205 }
1206 if (n == 0) {
1207 return 0;
1208 }
1209 const auto size {static_cast<std::size_t>(n)};
1210 const auto ld {static_cast<std::size_t>(lda)};
1211 std::vector<std::size_t> pivots;
1212 matrix<T> factors;
1213 bool singular {false};
1214 try { // B and A each transposed in and out once, in storage the thread keeps: the LU solves in B's copy and gives
1215 // its factors up
1216 buffer<T> a_rows {detail::take_kept<T>(0)};
1217 detail::row_major_into(a_rows, a, lda, n, n, T {1});
1218 lu_decomposition<T> lu {matrix<T> {size, size, std::move(a_rows)}};
1219 pivots = lu.pivots();
1220 singular = lu.singular();
1221 if (!singular && nrhs > 0) {
1222 // B = I (NumPy's inv) as the LU's inverse, its forward pass without the identity's zeros: the same terms
1223 // otherwise, so the same bits, where the right-hand sides are too many to go row by row.
1224 const bool inverting {nrhs == n && size > numerical::detail::narrow_solve && detail::is_identity(b, static_cast<std::size_t>(ldb), size)};
1225 buffer<T> b_rows {detail::take_kept<T>(1)};
1226 if (!inverting) {
1227 detail::row_major_into(b_rows, b, ldb, n, nrhs, T {1});
1228 }
1229 // (P A)⁻¹'s columns moved to A⁻¹'s as they are copied out.
1230 matrix<T> x {inverting ? lu.pivoted_inverse(std::move(b_rows)) : lu.solve(matrix<T> {size, static_cast<std::size_t>(nrhs), std::move(b_rows)})};
1231 if (inverting) {
1232 detail::column_major_permuted_into(&*x.begin(), size, lu.pivots().data(), b, static_cast<std::size_t>(ldb));
1233 }
1234 else {
1235 detail::column_major_into(&*x.begin(), size, static_cast<std::size_t>(nrhs), b, static_cast<std::size_t>(ldb));
1236 }
1237 detail::give_back(1, std::move(x).elements());
1238 }
1239 factors = std::move(lu).factors();
1240 }
1241 catch (const non_finite_error&) { // A and B untouched: dgetf2's factors, then getrs, the NaN carried through
1242 const int info {detail::rectangular_lu(size, size, a, ld, ipiv)};
1243 if (info == 0) {
1244 (void)getrs('N', n, nrhs, a, lda, ipiv, b, ldb); // its arguments already checked
1245 }
1246 return info;
1247 }
1248 detail::column_major_into(&*factors.begin(), size, size, a, ld);
1249 detail::give_back(0, std::move(factors).elements());
1250 detail::interchanges(pivots, ipiv);
1251 for (std::size_t i {0}; i < size; ++i) {
1252 if (a[i + (i * ld)] == T {}) { // U(i, i), as just written
1253 return static_cast<int>(i + 1);
1254 }
1255 }
1256 return 0;
1257 }
1258
1259 namespace detail {
1266 template <typename T>
1267 int column_cholesky(bool lower,
1268 std::size_t size,
1269 T* a,
1270 std::size_t ld)
1271 {
1272 // Element (i, j) of L: below the diagonal for lower, the conjugate of U's (j, i) above it otherwise.
1273 const auto l = [&](std::size_t i, std::size_t j) -> T& { return lower ? a[i + (j * ld)] : a[j + (i * ld)]; };
1274 const auto from_l = [&](T x) { return lower ? x : numerical::detail::conj_of(x); }; // L's value as stored
1275 for (std::size_t j {0}; j < size; ++j) {
1276 auto diagonal {std::real(a[j + (j * ld)])};
1277 for (std::size_t k {0}; k < j; ++k) {
1278 const T ljk {from_l(l(j, k))};
1279 diagonal -= std::real(ljk * numerical::detail::conj_of(ljk));
1280 }
1281 if (!(diagonal > 0)) { // not positive, or NaN
1282 a[j + (j * ld)] = T {diagonal};
1283 return static_cast<int>(j + 1);
1284 }
1285 diagonal = std::sqrt(diagonal);
1286 a[j + (j * ld)] = T {diagonal};
1287 for (std::size_t i {j + 1}; i < size; ++i) {
1288 T sum {from_l(l(i, j))};
1289 for (std::size_t k {0}; k < j; ++k) {
1290 sum -= from_l(l(i, k)) * numerical::detail::conj_of(from_l(l(j, k)));
1291 }
1292 l(i, j) = from_l(sum / diagonal);
1293 }
1294 }
1295 return 0;
1296 }
1297 } // namespace detail
1298
1309 template <typename T>
1310 int potrf(char uplo,
1311 std::ptrdiff_t n,
1312 T* a,
1313 std::ptrdiff_t lda)
1314 {
1315 const bool lower {uplo == 'L' || uplo == 'l'};
1316 if (!lower && uplo != 'U' && uplo != 'u') {
1317 return -1;
1318 }
1319 if (n < 0) {
1320 return -2;
1321 }
1322 if (lda < std::max<std::ptrdiff_t>(1, n)) {
1323 return -4;
1324 }
1325 if (n == 0) {
1326 return 0;
1327 }
1328 const auto size {static_cast<std::size_t>(n)};
1329 const auto ld {static_cast<std::size_t>(lda)};
1330 // A's lower triangle, row-major (the upper one's conjugate, Hermitian), in storage the thread keeps: the decomposition
1331 // reads no more of it and zeroes the rest. L's triangle by tiles (a row of it read across columns lda apart missed on
1332 // every element), U's columns as they lie; the factor written back the same ways.
1334 lower_rows.resize(size * size);
1335 if (lower) {
1336 detail::lower_triangle_rows(a, ld, size, lower_rows.data(), true);
1337 }
1338 else {
1339 for (std::size_t i {0}; i < size; ++i) {
1340 for (std::size_t j {0}; j <= i; ++j) {
1341 lower_rows[(i * size) + j] = numerical::detail::conj_of(a[j + (i * ld)]);
1342 }
1343 }
1344 }
1345 try {
1346 buffer<T> l {cholesky_decomposition<T> {matrix<T> {size, size, std::move(lower_rows)}}.lower().elements()};
1347 if (lower) {
1348 detail::lower_triangle_rows(a, ld, size, l.data(), false);
1349 }
1350 else { // U = Lᴴ
1351 for (std::size_t i {0}; i < size; ++i) {
1352 for (std::size_t j {0}; j <= i; ++j) {
1353 a[j + (i * ld)] = numerical::detail::conj_of(l[(i * size) + j]);
1354 }
1355 }
1356 }
1357 detail::give_back(0, std::move(l));
1358 }
1359 catch (const not_positive_definite_error& failed) {
1360 return static_cast<int>(failed.order());
1361 }
1362 catch (const non_finite_error&) { // A untouched: factorised as the reference's dpotf2 does, the NaN carried through
1363 return detail::column_cholesky(lower, size, a, ld);
1364 }
1365 return 0;
1366 }
1367
1375 template <typename T, typename Index>
1376 int getrf(std::ptrdiff_t m,
1377 std::ptrdiff_t n,
1378 T* a,
1379 std::ptrdiff_t lda,
1380 Index* ipiv)
1381 {
1382 if (m < 0) {
1383 return -1;
1384 }
1385 if (n < 0) {
1386 return -2;
1387 }
1388 if (lda < std::max<std::ptrdiff_t>(1, m)) {
1389 return -4;
1390 }
1391 if (m == 0 || n == 0) {
1392 return 0;
1393 }
1394 const auto rows {static_cast<std::size_t>(m)};
1395 const auto cols {static_cast<std::size_t>(n)};
1396 const auto ld {static_cast<std::size_t>(lda)};
1397 if (rows != cols) {
1398 return detail::rectangular_lu(rows, cols, a, ld, ipiv);
1399 }
1400 buffer<T> a_rows {detail::take_kept<T>(0)}; // transposed in and out once, in storage the thread keeps
1401 detail::row_major_into(a_rows, a, lda, m, n, T {1});
1402 std::optional<lu_decomposition<T>> factored; // a square A checked once, by the decomposition, where it was also
1403 try { // checked here, entry by entry across its columns
1404 factored.emplace(matrix<T> {rows, cols, std::move(a_rows)});
1405 }
1406 catch (const non_finite_error&) { // A untouched: factorised as the reference's dgetf2 does, the NaN carried through
1407 return detail::rectangular_lu(rows, cols, a, ld, ipiv);
1408 }
1410 detail::interchanges(lu.pivots(), ipiv);
1411 matrix<T> factors {std::move(lu).factors()};
1412 detail::column_major_into(&*factors.begin(), rows, cols, a, ld);
1413 detail::give_back(0, std::move(factors).elements());
1414 for (std::size_t i {0}; i < rows; ++i) {
1415 if (a[i + (i * ld)] == T {}) { // U(i, i), as just written
1416 return static_cast<int>(i + 1);
1417 }
1418 }
1419 return 0;
1420 }
1421
1428 template <typename T, typename Index>
1429 int getrs(char trans,
1430 std::ptrdiff_t n,
1431 std::ptrdiff_t nrhs,
1432 const T* a,
1433 std::ptrdiff_t lda,
1434 const Index* ipiv,
1435 T* b,
1436 std::ptrdiff_t ldb)
1437 {
1439 return -1;
1440 }
1441 if (n < 0) {
1442 return -2;
1443 }
1444 if (nrhs < 0) {
1445 return -3;
1446 }
1447 if (lda < std::max<std::ptrdiff_t>(1, n)) {
1448 return -5;
1449 }
1450 if (ldb < std::max<std::ptrdiff_t>(1, n)) {
1451 return -8;
1452 }
1453 const auto size {static_cast<std::size_t>(n)};
1454 const auto ld {static_cast<std::size_t>(lda)};
1455 detail::getrs_columns(trans, size, static_cast<std::size_t>(nrhs), a, ld, ipiv, b, static_cast<std::size_t>(ldb));
1456 return 0;
1457 }
1458
1459 namespace detail {
1462 template <typename T>
1463 void potrs_columns(bool lower,
1464 std::size_t size,
1465 std::size_t nrhs,
1466 const T* a,
1467 std::size_t ld,
1468 T* b,
1469 std::size_t ldb)
1470 {
1471 // L(i, j), i ≥ j: U(j, i) conjugated where U = Lᴴ is stored.
1472 const auto l = [&](std::size_t i, std::size_t j) { return lower ? a[i + (j * ld)] : numerical::detail::conj_of(a[j + (i * ld)]); };
1473 for (std::size_t c {0}; c < nrhs; ++c) {
1474 T* const x {b + (c * ldb)};
1475 for (std::size_t i {0}; i < size; ++i) { // L y = b
1476 T sum {x[i]};
1477 for (std::size_t k {0}; k < i; ++k) {
1478 sum -= l(i, k) * x[k];
1479 }
1480 x[i] = sum / l(i, i);
1481 }
1482 for (std::size_t i {size}; i-- > 0;) { // Lᴴ x = y
1483 T sum {x[i]};
1484 for (std::size_t k {i + 1}; k < size; ++k) {
1485 sum -= numerical::detail::conj_of(l(k, i)) * x[k];
1486 }
1487 x[i] = sum / numerical::detail::conj_of(l(i, i));
1488 }
1489 }
1490 }
1491
1494 inline void potrs_columns(bool lower,
1495 std::size_t size,
1496 std::size_t nrhs,
1497 const double* a,
1498 std::size_t ld,
1499 double* b,
1500 std::size_t ldb)
1501 {
1502 if (nrhs < trsm_columns_least) { // a few columns: trsm's copy of op(A) outweighs its blocks
1503 potrs_columns<double>(lower, size, nrhs, a, ld, b, ldb);
1504 return;
1505 }
1506 const auto n {static_cast<std::ptrdiff_t>(size)};
1507 const auto columns {static_cast<std::ptrdiff_t>(nrhs)};
1508 const char uplo {lower ? 'L' : 'U'};
1509 (void)trsm('L', uplo, lower ? 'N' : 'T', 'N', n, columns, 1.0, a, static_cast<std::ptrdiff_t>(ld), b, static_cast<std::ptrdiff_t>(ldb));
1510 (void)trsm('L', uplo, lower ? 'T' : 'N', 'N', n, columns, 1.0, a, static_cast<std::ptrdiff_t>(ld), b, static_cast<std::ptrdiff_t>(ldb));
1511 }
1512 } // namespace detail
1513
1520 template <typename T>
1521 int potrs(char uplo,
1522 std::ptrdiff_t n,
1523 std::ptrdiff_t nrhs,
1524 const T* a,
1525 std::ptrdiff_t lda,
1526 T* b,
1527 std::ptrdiff_t ldb)
1528 {
1529 const bool lower {uplo == 'L' || uplo == 'l'};
1530 if (!lower && uplo != 'U' && uplo != 'u') {
1531 return -1;
1532 }
1533 if (n < 0) {
1534 return -2;
1535 }
1536 if (nrhs < 0) {
1537 return -3;
1538 }
1539 if (lda < std::max<std::ptrdiff_t>(1, n)) {
1540 return -5;
1541 }
1542 if (ldb < std::max<std::ptrdiff_t>(1, n)) {
1543 return -7;
1544 }
1545 const auto size {static_cast<std::size_t>(n)};
1546 const auto ld {static_cast<std::size_t>(lda)};
1547 detail::potrs_columns(lower, size, static_cast<std::size_t>(nrhs), a, ld, b, static_cast<std::size_t>(ldb));
1548 return 0;
1549 }
1550
1562 template <typename Index>
1563 int syevd(char jobz,
1564 char uplo,
1565 std::ptrdiff_t n,
1566 double* a,
1567 std::ptrdiff_t lda,
1568 double* w,
1569 double* work,
1570 std::ptrdiff_t lwork,
1571 Index* iwork,
1572 std::ptrdiff_t liwork)
1573 {
1574 const bool vectors {jobz == 'V' || jobz == 'v'};
1575 const bool lower {uplo == 'L' || uplo == 'l'};
1576 if (!vectors && jobz != 'N' && jobz != 'n') {
1577 return -1;
1578 }
1579 if (!lower && uplo != 'U' && uplo != 'u') {
1580 return -2;
1581 }
1582 if (n < 0) {
1583 return -3;
1584 }
1585 if (lda < std::max<std::ptrdiff_t>(1, n)) {
1586 return -5;
1587 }
1588 std::ptrdiff_t lwork_least {1};
1589 std::ptrdiff_t liwork_least {1};
1590 if (n > 1) {
1591 lwork_least = vectors ? 1 + (6 * n) + (2 * n * n) : (2 * n) + 1;
1592 liwork_least = vectors ? 3 + (5 * n) : 1;
1593 }
1594 if (lwork == -1 || liwork == -1) {
1595 work[0] = static_cast<double>(lwork_least);
1596 iwork[0] = static_cast<Index>(liwork_least);
1597 return 0;
1598 }
1599 if (lwork < lwork_least) {
1600 return -8;
1601 }
1602 if (liwork < liwork_least) {
1603 return -10;
1604 }
1605 if (n == 0) {
1606 return 0;
1607 }
1608 const auto size {static_cast<std::size_t>(n)};
1609 const auto ld {static_cast<std::size_t>(lda)};
1610 buffer<double> lower_rows(size * size, 0.0); // the triangle read, as the lower one, row-major
1611 for (std::size_t i {0}; i < size; ++i) {
1612 for (std::size_t j {0}; j <= i; ++j) {
1613 lower_rows[(i * size) + j] = lower ? a[i + (j * ld)] : a[j + (i * ld)];
1614 }
1615 }
1616 try {
1617 const matrix<double> symmetric {size, size, std::move(lower_rows)};
1618 if (!vectors) {
1620 std::copy_n(&values[0], size, w);
1621 return 0;
1622 }
1624 std::copy_n(&eigen.values()[0], size, w);
1625 for (std::size_t j {0}; j < size; ++j) {
1626 for (std::size_t i {0}; i < size; ++i) {
1627 a[i + (j * ld)] = eigen.vectors()(i, j);
1628 }
1629 }
1630 }
1631 catch (const non_finite_error&) { // as the reference's divide and conquer on a NaN: no eigenvalue converges
1632 std::fill_n(w, size, std::numeric_limits<double>::quiet_NaN());
1633 if (vectors) {
1634 for (std::size_t j {0}; j < size; ++j) {
1635 std::fill_n(a + (j * ld), size, std::numeric_limits<double>::quiet_NaN());
1636 }
1637 }
1638 return static_cast<int>(size);
1639 }
1640 return 0;
1641 }
1642
1652 template <typename Index>
1653 int gesdd(char jobz,
1654 std::ptrdiff_t m,
1655 std::ptrdiff_t n,
1656 double* a,
1657 std::ptrdiff_t lda,
1658 double* s,
1659 double* u,
1660 std::ptrdiff_t ldu,
1661 double* vt,
1662 std::ptrdiff_t ldvt,
1663 double* work,
1664 std::ptrdiff_t lwork,
1665 Index* iwork)
1666 {
1667 (void)iwork; // dgesdd's integer workspace, of 8 min(m, n): not used
1668 const bool all {jobz == 'A' || jobz == 'a'};
1669 const bool some {jobz == 'S' || jobz == 's'};
1670 const bool overwrite {jobz == 'O' || jobz == 'o'};
1671 const bool none {jobz == 'N' || jobz == 'n'};
1672 if (!all && !some && !overwrite && !none) {
1673 return -1;
1674 }
1675 if (m < 0) {
1676 return -2;
1677 }
1678 if (n < 0) {
1679 return -3;
1680 }
1681 if (lda < std::max<std::ptrdiff_t>(1, m)) {
1682 return -5;
1683 }
1684 const std::ptrdiff_t least {std::min(m, n)};
1685 const std::ptrdiff_t most {std::max(m, n)};
1686 const bool u_out {all || some || (overwrite && m < n)};
1687 const bool vt_out {all || some || (overwrite && m >= n)};
1688 if (ldu < std::max<std::ptrdiff_t>(1, u_out ? m : 1)) {
1689 return -8;
1690 }
1691 std::ptrdiff_t vt_rows {1};
1692 if (some) {
1693 vt_rows = least;
1694 }
1695 else if (vt_out) { // A, or O with m ≥ n: Vᵀ whole
1696 vt_rows = n;
1697 }
1698 if (ldvt < std::max<std::ptrdiff_t>(1, vt_rows)) {
1699 return -10;
1700 }
1701 std::ptrdiff_t lwork_least {(3 * least) + std::max(most, 7 * least)};
1702 if (overwrite) {
1703 lwork_least = (3 * least) + std::max(most, (5 * least * least) + (4 * least));
1704 }
1705 else if (all || some) {
1706 lwork_least = (3 * least) + std::max(most, (4 * least * least) + (4 * least));
1707 }
1708 if (lwork == -1) {
1709 work[0] = static_cast<double>(std::max<std::ptrdiff_t>(1, lwork_least));
1710 return 0;
1711 }
1712 if (lwork < std::max<std::ptrdiff_t>(1, lwork_least)) {
1713 return -12;
1714 }
1715 if (least == 0) {
1716 return 0;
1717 }
1718 const auto rows {static_cast<std::size_t>(m)};
1719 const auto cols {static_cast<std::size_t>(n)};
1720 const auto k {static_cast<std::size_t>(least)};
1721 try {
1722 const matrix<double> source {rows, cols, detail::row_major(a, lda, m, n, 1.0)};
1723 if (none) {
1724 const vector<double> values {singular_values(source)};
1725 std::copy_n(&values[0], k, s);
1726 return 0;
1727 }
1729 std::copy_n(&svd.singular_values()[0], k, s);
1730 const matrix<double> left {svd.u()};
1731 const matrix<double> right {svd.vh()};
1732 // With O, the factor that fits A's storage goes there, the other to its own argument.
1733 double* const u_into {overwrite && m >= n ? a : u};
1734 const std::size_t ld_u {overwrite && m >= n ? static_cast<std::size_t>(lda) : static_cast<std::size_t>(ldu)};
1735 double* const vt_into {overwrite && m < n ? a : vt};
1736 const std::size_t ld_vt {overwrite && m < n ? static_cast<std::size_t>(lda) : static_cast<std::size_t>(ldvt)};
1737 for (std::size_t j {0}; j < left.cols(); ++j) {
1738 for (std::size_t i {0}; i < left.rows(); ++i) {
1739 u_into[i + (j * ld_u)] = left(i, j);
1740 }
1741 }
1742 for (std::size_t j {0}; j < right.cols(); ++j) {
1743 for (std::size_t i {0}; i < right.rows(); ++i) {
1744 vt_into[i + (j * ld_vt)] = right(i, j);
1745 }
1746 }
1747 }
1748 catch (const non_finite_error&) {
1749 return -4;
1750 }
1751 return 0;
1752 }
1753
1764 inline int geqrf(std::ptrdiff_t m,
1765 std::ptrdiff_t n,
1766 double* a,
1767 std::ptrdiff_t lda,
1768 double* tau,
1769 double* work,
1770 std::ptrdiff_t lwork)
1771 {
1772 if (m < 0) {
1773 return -1;
1774 }
1775 if (n < 0) {
1776 return -2;
1777 }
1778 if (lda < std::max<std::ptrdiff_t>(1, m)) {
1779 return -4;
1780 }
1781 const std::ptrdiff_t lwork_least {std::min(m, n) == 0 ? 1 : n};
1782 if (lwork == -1) {
1783 work[0] = static_cast<double>(lwork_least);
1784 return 0;
1785 }
1786 if (lwork < lwork_least) {
1787 return -7;
1788 }
1789 if (std::min(m, n) == 0) {
1790 return 0;
1791 }
1792 const auto rows {static_cast<std::size_t>(m)};
1793 const auto cols {static_cast<std::size_t>(n)};
1794 const auto ld {static_cast<std::size_t>(lda)};
1795 // In the layout the factorisation runs in (numerical::detail::householder_reflect), in storage the thread keeps: R and
1796 // the reflectors' w₁… where dgeqrf leaves them (numerical::detail::factor_qr_panel, as dlarfg); τ on each block's T
1797 // diagonal, 0 for the identity.
1799#ifdef NUMERICAL_X86_COMPILED
1800 entries.resize(rows * cols); // column-major: copied in and out by columns
1801 for (std::size_t j {0}; j < cols; ++j) {
1802 std::copy_n(a + (j * ld), rows, entries.data() + (j * rows));
1803 }
1804#else
1805 detail::row_major_into(entries, a, lda, m, n, 1.0);
1806#endif
1807#ifdef NUMERICAL_X86_COMPILED
1808 const std::vector<numerical::detail::reflector_block<double>> blocks {numerical::detail::reflect_in_columns(entries, rows, cols)};
1809 for (std::size_t j {0}; j < cols; ++j) {
1810 std::copy_n(entries.data() + (j * rows), rows, a + (j * ld));
1811 }
1812#else
1813 const std::vector<numerical::detail::reflector_block<double>> blocks {numerical::detail::reflect_in_rows(entries, rows, cols)};
1814 detail::column_major_into(entries.data(), rows, cols, a, ld);
1815#endif
1816 detail::give_back(0, std::move(entries));
1817 for (const numerical::detail::reflector_block<double>& block : blocks) {
1818 for (std::size_t j {0}; j < block.width; ++j) {
1819 tau[block.first + j] = block.t[(j * block.width) + j];
1820 }
1821 }
1822 return 0;
1823 }
1824
1834 inline int orgqr(std::ptrdiff_t m,
1835 std::ptrdiff_t n,
1836 std::ptrdiff_t k,
1837 double* a,
1838 std::ptrdiff_t lda,
1839 const double* tau,
1840 double* work,
1841 std::ptrdiff_t lwork)
1842 {
1843 if (m < 0) {
1844 return -1;
1845 }
1846 if (n < 0 || n > m) {
1847 return -2;
1848 }
1849 if (k < 0 || k > n) {
1850 return -3;
1851 }
1852 if (lda < std::max<std::ptrdiff_t>(1, m)) {
1853 return -5;
1854 }
1855 const std::ptrdiff_t lwork_least {std::max<std::ptrdiff_t>(1, n)};
1856 if (lwork == -1) {
1857 work[0] = static_cast<double>(lwork_least);
1858 return 0;
1859 }
1860 if (lwork < lwork_least) {
1861 return -8;
1862 }
1863 if (n == 0) {
1864 return 0;
1865 }
1866 const auto rows {static_cast<std::size_t>(m)};
1867 const auto cols {static_cast<std::size_t>(n)};
1868 const auto depth {static_cast<std::size_t>(k)};
1869 const auto ld {static_cast<std::size_t>(lda)};
1870 // Each reflector w_j = (1, A(j+1…m-1, j)) and τ_j, gathered by blocks into I − V T Vᵀ (T as dlarft forms it).
1871 std::vector<buffer<double>> reflectors(depth);
1872 const std::vector<double> taus(tau, tau + depth);
1873 for (std::size_t j {0}; j < depth; ++j) {
1874 reflectors[j].resize(rows - j);
1875 reflectors[j][0] = 1.0;
1876 std::copy_n(a + (j + 1) + (j * ld), rows - j - 1, reflectors[j].data() + 1);
1877 }
1878 std::vector<numerical::detail::reflector_block<double>> blocks;
1879 for (std::size_t k0 {0}; k0 < depth; k0 += numerical::detail::qr_block) {
1880 blocks.push_back(numerical::detail::gather_reflectors(reflectors, k0, std::min(k0 + numerical::detail::qr_block, depth), rows, &taus));
1881 }
1882 buffer<double> columns {detail::take_kept<double>(0)}; // Q column-major, as numerical::qr() forms it
1883 numerical::detail::form_q_into(columns, blocks, rows, 0, cols, true);
1884 for (std::size_t j {0}; j < cols; ++j) {
1885 std::copy_n(columns.data() + (j * rows), rows, a + (j * ld));
1886 }
1887 detail::give_back(0, std::move(columns));
1888 return 0;
1889 }
1890
1902 template <typename Index>
1903 int gelsd(std::ptrdiff_t m,
1904 std::ptrdiff_t n,
1905 std::ptrdiff_t nrhs,
1906 const double* a,
1907 std::ptrdiff_t lda,
1908 double* b,
1909 std::ptrdiff_t ldb,
1910 double* s,
1911 double rcond,
1912 Index* rank,
1913 double* work,
1914 std::ptrdiff_t lwork,
1915 Index* iwork)
1916 {
1917 if (m < 0) {
1918 return -1;
1919 }
1920 if (n < 0) {
1921 return -2;
1922 }
1923 if (nrhs < 0) {
1924 return -3;
1925 }
1926 if (lda < std::max<std::ptrdiff_t>(1, m)) {
1927 return -5;
1928 }
1929 if (ldb < std::max<std::ptrdiff_t>({1, m, n})) {
1930 return -7;
1931 }
1932 // dgelsd's sizes: its divide and conquer's leaves of 25 values, NLVL levels above them.
1933 constexpr std::ptrdiff_t leaf {25};
1934 const std::ptrdiff_t least {std::max<std::ptrdiff_t>(1, std::min(m, n))};
1935 const auto levels {std::max<std::ptrdiff_t>(
1936 static_cast<std::ptrdiff_t>(std::log2(static_cast<double>(least) / static_cast<double>(leaf + 1))) + 1, 0)};
1937 const std::ptrdiff_t lwork_least {(3 * least) + (9 * least) + (2 * least * leaf) + (8 * least * levels) + (least * nrhs)
1938 + ((leaf + 1) * (leaf + 1))};
1939 if (lwork == -1) {
1940 work[0] = static_cast<double>(lwork_least);
1941 iwork[0] = static_cast<Index>((3 * least * levels) + (11 * least));
1942 return 0;
1943 }
1944 if (lwork < lwork_least) {
1945 return -12;
1946 }
1947 *rank = 0;
1948 if (m == 0 || n == 0) {
1949 return 0;
1950 }
1951 const auto rows {static_cast<std::size_t>(m)};
1952 const auto cols {static_cast<std::size_t>(n)};
1953 const auto rhs {static_cast<std::size_t>(nrhs)};
1954 const auto ld {static_cast<std::size_t>(ldb)};
1955 buffer<double> right(rows * rhs, 0.0);
1956 for (std::size_t i {0}; i < rows; ++i) {
1957 for (std::size_t c {0}; c < rhs; ++c) {
1958 right[(i * rhs) + c] = b[i + (c * ld)];
1959 }
1960 }
1961 if (!std::ranges::all_of(right, [](double x) { return std::isfinite(x); })) {
1962 return -6;
1963 }
1965 try {
1966 const matrix<double> left {rows, cols, detail::row_major(a, lda, m, n, 1.0)};
1968 std::copy_n(&fit.singular_values[0], fit.singular_values.size(), s);
1969 *rank = static_cast<Index>(fit.rank);
1970 for (std::size_t c {0}; c < rhs; ++c) {
1971 for (std::size_t i {0}; i < cols; ++i) {
1972 b[i + (c * ld)] = fit.solution(i, c);
1973 }
1974 for (std::size_t i {cols}; i < rows; ++i) {
1975 b[i + (c * ld)] = i == cols && fit.residuals.size() > 0 ? std::sqrt(fit.residuals[c]) : 0.0;
1976 }
1977 }
1978 }
1979 catch (const non_finite_error&) {
1980 return -4;
1981 }
1982 return 0;
1983 }
1984
1985 namespace detail {
1986
1990 inline void real_form(const matrix<std::complex<double>>& v,
1991 const vector<std::complex<double>>& values,
1992 double* out,
1993 std::size_t ld)
1994 {
1995 const std::size_t n {values.size()};
1996 for (std::size_t j {0}; j < n; ++j) {
1997 if (values[j].imag() == 0.0) {
1998 for (std::size_t i {0}; i < n; ++i) {
1999 out[i + (j * ld)] = v(i, j).real();
2000 }
2001 }
2002 else if (values[j].imag() > 0.0) {
2003 for (std::size_t i {0}; i < n; ++i) {
2004 out[i + (j * ld)] = v(i, j).real();
2005 out[i + ((j + 1) * ld)] = v(i, j).imag();
2006 }
2007 }
2008 }
2009 }
2010 } // namespace detail
2011
2024 inline int geev(char jobvl,
2025 char jobvr,
2026 std::ptrdiff_t n,
2027 const double* a,
2028 std::ptrdiff_t lda,
2029 double* wr,
2030 double* wi,
2031 double* vl,
2032 std::ptrdiff_t ldvl,
2033 double* vr,
2034 std::ptrdiff_t ldvr,
2035 double* work,
2036 std::ptrdiff_t lwork)
2037 {
2038 const bool left {jobvl == 'V' || jobvl == 'v'};
2039 const bool right {jobvr == 'V' || jobvr == 'v'};
2040 if (!left && jobvl != 'N' && jobvl != 'n') {
2041 return -1;
2042 }
2043 if (!right && jobvr != 'N' && jobvr != 'n') {
2044 return -2;
2045 }
2046 if (n < 0) {
2047 return -3;
2048 }
2049 if (lda < std::max<std::ptrdiff_t>(1, n)) {
2050 return -5;
2051 }
2052 if (ldvl < 1 || (left && ldvl < n)) {
2053 return -9;
2054 }
2055 if (ldvr < 1 || (right && ldvr < n)) {
2056 return -11;
2057 }
2058 const std::ptrdiff_t lwork_least {std::max<std::ptrdiff_t>(1, (left || right ? 4 : 3) * n)};
2059 if (lwork == -1) {
2060 work[0] = static_cast<double>(lwork_least);
2061 return 0;
2062 }
2063 if (lwork < lwork_least) {
2064 return -13;
2065 }
2066 if (n == 0) {
2067 return 0;
2068 }
2069 const auto size {static_cast<std::size_t>(n)};
2070 try {
2071 const matrix<double> source {size, size, detail::row_major(a, lda, n, n, 1.0)};
2072 const eigen_decomposition<double> eigen {source, right, left}; // both sides from one Schur form
2073 const vector<std::complex<double>>& values {eigen.values()};
2074 for (std::size_t j {0}; j < size; ++j) {
2075 wr[j] = values[j].real();
2076 wi[j] = values[j].imag();
2077 }
2078 if (right) {
2079 detail::real_form(eigen.vectors(), values, vr, static_cast<std::size_t>(ldvr));
2080 }
2081 if (left) {
2082 detail::real_form(eigen.left_vectors(), values, vl, static_cast<std::size_t>(ldvl));
2083 }
2084 }
2085 catch (const non_finite_error&) {
2086 return -4;
2087 }
2088 return 0;
2089 }
2090} // namespace numerical::blas
2091
2092#endif // NUMERICAL_BLAS_HPP
A Cholesky factorisation A = L Lᴴ of a Hermitian positive-definite matrix.
The eigenvalues, and optionally the right eigenvectors, of a general square matrix,...
Definition eigen.hpp:3113
An LU factorisation with partial pivoting of a square matrix: each column's pivot the first entry of ...
A dense, row-major matrix of T with value semantics.
Definition matrix.hpp:36
buffer< T >::const_iterator begin() const noexcept
Const iterator to the first element (row-major).
Definition matrix.hpp:133
buffer< T > elements() &&
The elements, row-major, handed over by a matrix about to expire, which is left 0 × 0: a large result...
Definition matrix.hpp:146
Thrown when a decomposition's input holds an infinite or NaN entry: no factorisation of it means anyt...
Thrown when a Cholesky factorisation finds the matrix not positive-definite.
std::size_t order() const noexcept
The order of the first leading minor found not positive definite (LAPACK's info), 0 where unknown.
The magnitude at or under which a singular value counts as zero, in a rank (matrix_rank),...
static rank_cutoff relative(double ratio)
The largest singular value times ratio.
The singular value decomposition A = U Σ Vᴴ of an m × n matrix.
Definition svd.hpp:1601
The eigenvalues and eigenvectors of a real symmetric matrix.
A dense vector of T with value semantics.
Definition vector.hpp:171
Matrix factorisations and the algorithms built on them.
The eigenvalues and eigenvectors of a general square matrix.
The matrix product kernel behind matrix * matrix and the einsum matmul path.
A dense, row-major, value-semantic matrix over a scalar type.
void potrs_columns(bool lower, std::size_t size, std::size_t nrhs, const T *a, std::size_t ld, T *b, std::size_t ldb)
potrs's solves, each column of B by forward then backward substitution with L (lower) or Uᴴ (size × n...
Definition blas.hpp:1463
void syrk_product(const syrk_operands &operands, std::size_t c0, std::size_t cols, std::size_t r0, std::size_t rows, double *out, std::size_t ldo)
P(c0…) Q(…, r0…) added to the cols × rows row-major block at out (ldo apart): numerical::detail::gemm...
Definition blas.hpp:743
void syrk_triangle(syrk_operands operands, std::size_t j0, std::size_t w)
Adds P Q to the triangle of the diagonal block [j0, j0 + w) of C: halved until it is a block of syrk_...
Definition blas.hpp:769
buffer< double > & syrk_operand() noexcept
The storage of syrk's operand copy this thread keeps between calls.
Definition blas.hpp:52
void lower_triangle_rows(T *a, std::size_t lda, std::size_t n, T *rows, bool in)
The lower triangle of the column-major n × n a (lda apart) into that of the row-major rows (n apart) ...
Definition blas.hpp:288
buffer< T > & kept_storage(std::size_t slot) noexcept
Row-major storage of the scalar T this thread keeps between calls, in slot (0 for a call's A,...
Definition blas.hpp:155
bool is_identity(const T *b, std::size_t ldb, std::size_t n)
Whether the column-major n × n b (ldb apart) is the identity to the bit (a -0 is no zero of it,...
Definition blas.hpp:186
void triangular_solve(bool lower, bool unit, std::size_t k, std::size_t n, const double *a, std::size_t lda, double *b, std::size_t ldb)
A X = B in place for the column-major triangular k × k a (lower or upper, a unit diagonal not read) a...
Definition blas.hpp:925
constexpr std::size_t strided(std::size_t i, std::size_t length, std::ptrdiff_t inc) noexcept
Index of element i of a BLAS vector of length elements inc apart: from the last one where inc is nega...
Definition blas.hpp:537
bool finite(const T &x)
Whether the real x is finite (an overload per kind of scalar, as conj_of: each one expression).
Definition blas.hpp:79
void column_major_permuted_into(const T *from, std::size_t n, const std::size_t *to, T *a, std::size_t lda)
column_major_into for the n × n from, its column j written as column to[j] of a.
Definition blas.hpp:225
constexpr bool is_operation(char op) noexcept
Whether op is one of BLAS's N, T or C (either case): no transpose, transpose, conjugate one.
Definition blas.hpp:60
constexpr std::size_t kept_bytes
The most bytes a thread keeps in each of kept_storage's slots between calls (32 MiB).
Definition blas.hpp:147
int rectangular_lu(std::size_t m, std::size_t n, T *a, std::size_t lda, Index *ipiv)
The LU factorisation with partial pivoting of a rectangular column-major A in place,...
Definition blas.hpp:423
void give_back(std::size_t slot, buffer< T > &&storage)
storage given back to kept_storage's slot, unless past kept_bytes.
Definition blas.hpp:171
void interchanges(const std::vector< std::size_t > &pivots, Index *ipiv)
The permutation pivots (row i of P A is row pivots[i] of A) as LAPACK's successive row interchanges,...
Definition blas.hpp:399
void getrs_columns(char trans, std::size_t size, std::size_t nrhs, const T *a, std::size_t ld, const Index *ipiv, T *b, std::size_t ldb)
getrs's solves, each column of B by forward then backward substitution (size × nrhs,...
Definition blas.hpp:1069
constexpr bool conjugates(char op) noexcept
Whether op is BLAS's C: the conjugate transpose (a real matrix's is its transpose).
Definition blas.hpp:72
void row_major_into(buffer< T > &out, const T *a, std::ptrdiff_t lda, std::ptrdiff_t rows, std::ptrdiff_t cols, T scale, bool conjugate=false)
The column-major rows × cols a (lda apart) into the row-major out (resized to it),...
Definition blas.hpp:105
void column_major_into(const T *from, std::size_t rows, std::size_t cols, T *a, std::size_t lda)
The row-major rows × cols from into the column-major a (lda apart), by tiles.
Definition blas.hpp:207
buffer< T > row_major(const T *a, std::ptrdiff_t lda, std::ptrdiff_t rows, std::ptrdiff_t cols, T scale, bool conjugate=false)
rows × cols of the column-major a (lda apart), as a row-major buffer, each element times scale (conju...
Definition blas.hpp:134
buffer< T > take_kept(std::size_t slot)
kept_storage's slot, taken over by the caller (left empty there meanwhile).
Definition blas.hpp:164
void product_by_op_a(char transa, std::size_t m, std::size_t n, std::size_t k, const T *l, std::size_t ldl, const T *a, std::size_t lda, T *c, std::size_t ldc)
C += L op(A)ᵀ (C row-major m × n, L m × k), a the column-major op(A)'s storage (lda apart): op(A)ᵀ is...
Definition blas.hpp:247
int column_cholesky(bool lower, std::size_t size, T *a, std::size_t ld)
The Cholesky factor of the column-major order-size A in place, column by column as the reference's dp...
Definition blas.hpp:1267
void syrk_all(const syrk_operands &operands, std::size_t n)
The whole triangle of C (order n) from operands: a product the matrix product kernel packs runs in on...
Definition blas.hpp:799
buffer< T > columns_as_rows(const T *a, std::ptrdiff_t lda, std::ptrdiff_t rows, std::ptrdiff_t cols, T scale)
The cols columns of rows elements of the column-major a (lda apart) as the rows of a row-major buffer...
Definition blas.hpp:317
constexpr bool transposes(char op) noexcept
Whether op transposes (T or C: a real matrix's conjugate transpose is its transpose).
Definition blas.hpp:66
constexpr std::size_t trsm_columns_least
The fewest columns of B getrs and potrs of double solve by trsm: fewer take the substitution column b...
Definition blas.hpp:1064
constexpr std::size_t transpose_weight
The weight of an element of the transposing copies against a multiply-add: bound by the memory,...
Definition blas.hpp:100
T real_dot(std::ptrdiff_t n, const T *x, std::ptrdiff_t incx, const T *y, std::ptrdiff_t incy)
numerical::blas::dot of the real scalar T.
Definition blas.hpp:547
constexpr std::size_t transpose_tile
The tile side of the transposing copies between column-major arguments and row-major storage: a tile'...
Definition blas.hpp:94
void real_form(const matrix< std::complex< double > > &v, const vector< std::complex< double > > &values, double *out, std::size_t ld)
The eigenvectors v (columns, complex, matching values) in dgeev's real form, into the column-major ou...
Definition blas.hpp:1990
void product_of_ops(char transa, char transb, T alpha, std::size_t m, std::size_t n, std::size_t k, const T *a, std::size_t lda, const T *b, std::size_t ldb, T *c, std::size_t ldc)
C += α op(B)ᵀ op(A)ᵀ, row-major C (m × n, ldc apart), the column-major C of BLAS's gemm as its transp...
Definition blas.hpp:341
std::complex< T > complex_dot(bool conjugate, std::ptrdiff_t n, const std::complex< T > *x, std::ptrdiff_t incx, const std::complex< T > *y, std::ptrdiff_t incy) noexcept
Σ x_i y_i (conjugate false, BLAS's zdotu) or Σ conj(x_i) y_i (true, zdotc) over n complex elements in...
Definition blas.hpp:602
int potrf(char uplo, std::ptrdiff_t n, T *a, std::ptrdiff_t lda)
The Cholesky factor of a symmetric positive-definite A, column-major, as LAPACK's dpotrf: with uplo L...
Definition blas.hpp:1310
int gemm(char transa, char transb, std::ptrdiff_t m, std::ptrdiff_t n, std::ptrdiff_t k, T alpha, const T *a, std::ptrdiff_t lda, const T *b, std::ptrdiff_t ldb, T beta, T *c, std::ptrdiff_t ldc)
C ← α op(A) op(B) + β C, column-major, as BLAS's dgemm: op(A) is m × k, op(B) k × n,...
Definition blas.hpp:469
double dot(std::ptrdiff_t n, const double *x, std::ptrdiff_t incx, const double *y, std::ptrdiff_t incy)
Σ x_i y_i over n elements incx and incy apart (from the last where negative), as BLAS's ddot; 0 where...
Definition blas.hpp:575
int getrf(std::ptrdiff_t m, std::ptrdiff_t n, T *a, std::ptrdiff_t lda, Index *ipiv)
P A = L U of the column-major m × n A in place, as LAPACK's dgetrf: the factors as dgetrf leaves them...
Definition blas.hpp:1376
int trsm(char side, char uplo, char transa, char diag, std::ptrdiff_t m, std::ptrdiff_t n, double alpha, const double *a, std::ptrdiff_t lda, double *b, std::ptrdiff_t ldb)
B ← α op(A)⁻¹ B (side L) or α B op(A)⁻¹ (R), column-major, B m × n and the triangular A (uplo U or L,...
Definition blas.hpp:970
constexpr std::size_t syrk_block
The columns of syrk's smallest diagonal blocks, formed whole: their wasted half, at most 64 n k multi...
Definition blas.hpp:44
int orgqr(std::ptrdiff_t m, std::ptrdiff_t n, std::ptrdiff_t k, double *a, std::ptrdiff_t lda, const double *tau, double *work, std::ptrdiff_t lwork)
The first n columns of Q = H₀ H₁ … H_{k-1}, from the reflectors of a dgeqrf (geqrf's or any implement...
Definition blas.hpp:1834
constexpr double lapack_precision
LAPACK's relative machine precision, ‘dlamch('E’): the unit roundoff2⁻⁵³, half of std::numeric_limits...
Definition blas.hpp:40
constexpr std::size_t trsm_block
The rows of trsm's blocks: within one, each column solved alone; past it, the matrix product kernel.
Definition blas.hpp:915
int syevd(char jobz, char uplo, std::ptrdiff_t n, double *a, std::ptrdiff_t lda, double *w, double *work, std::ptrdiff_t lwork, Index *iwork, std::ptrdiff_t liwork)
The eigenvalues, and with jobz V the eigenvectors, of a symmetric column-major A, as LAPACK's dsyevd:...
Definition blas.hpp:1563
int gesdd(char jobz, std::ptrdiff_t m, std::ptrdiff_t n, double *a, std::ptrdiff_t lda, double *s, double *u, std::ptrdiff_t ldu, double *vt, std::ptrdiff_t ldvt, double *work, std::ptrdiff_t lwork, Index *iwork)
The singular value decomposition A = U Σ Vᵀ of a column-major m × n A, as LAPACK's dgesdd: the singul...
Definition blas.hpp:1653
constexpr std::size_t syrk_kept_limit
The most elements of syrk's operand copy a thread keeps between calls (32 MiB).
Definition blas.hpp:47
int gemv(char trans, std::ptrdiff_t m, std::ptrdiff_t n, double alpha, const double *a, std::ptrdiff_t lda, const double *x, std::ptrdiff_t incx, double beta, double *y, std::ptrdiff_t incy)
y ← α op(A) x + β y, column-major A m × n, as BLAS's dgemv: the vectors incx and incy apart (from the...
Definition blas.hpp:640
int geev(char jobvl, char jobvr, std::ptrdiff_t n, const double *a, std::ptrdiff_t lda, double *wr, double *wi, double *vl, std::ptrdiff_t ldvl, double *vr, std::ptrdiff_t ldvr, double *work, std::ptrdiff_t lwork)
The eigenvalues, and with jobvl or jobvr V the left or right eigenvectors, of a column-major n × n A,...
Definition blas.hpp:2024
int potrs(char uplo, std::ptrdiff_t n, std::ptrdiff_t nrhs, const T *a, std::ptrdiff_t lda, T *b, std::ptrdiff_t ldb)
A X = B from the Cholesky factor of a dpotrf (by any implementation), column-major,...
Definition blas.hpp:1521
int getrs(char trans, std::ptrdiff_t n, std::ptrdiff_t nrhs, const T *a, std::ptrdiff_t lda, const Index *ipiv, T *b, std::ptrdiff_t ldb)
A X = B, Aᵀ X = B or Aᴴ X = B (trans N, T or C), column-major, from the factors and interchanges of a...
Definition blas.hpp:1429
int syrk(char uplo, char trans, std::ptrdiff_t n, std::ptrdiff_t k, double alpha, const double *a, std::ptrdiff_t lda, double beta, double *c, std::ptrdiff_t ldc)
C ← α op(A) op(A)ᵀ + β C on the triangle uplo (U or L) of the column-major n × n C,...
Definition blas.hpp:830
int gesv(std::ptrdiff_t n, std::ptrdiff_t nrhs, T *a, std::ptrdiff_t lda, Index *ipiv, T *b, std::ptrdiff_t ldb)
A X = B, column-major, as LAPACK's dgesv: A (n × n, lda apart) is factorised as P A = L U by NumericA...
Definition blas.hpp:1186
int gelsd(std::ptrdiff_t m, std::ptrdiff_t n, std::ptrdiff_t nrhs, const double *a, std::ptrdiff_t lda, double *b, std::ptrdiff_t ldb, double *s, double rcond, Index *rank, double *work, std::ptrdiff_t lwork, Index *iwork)
The minimum-norm least-squares solutions of A X ≈ B, column-major A m × n and B max(m,...
Definition blas.hpp:1903
constexpr std::size_t gemv_rows
The rows (or, for Aᵀ x, the columns) each task of gemv takes, 64 so that an order of a few hundred sh...
Definition blas.hpp:626
int geqrf(std::ptrdiff_t m, std::ptrdiff_t n, double *a, std::ptrdiff_t lda, double *tau, double *work, std::ptrdiff_t lwork)
The QR factorisation A = Q R of a column-major m × n A, as LAPACK's dgeqrf: R overwrites the upper tr...
Definition blas.hpp:1764
constexpr std::size_t gemv_weight
The weight of gemv's multiply-adds against a compute-bound product's: each reads an element of A once...
Definition blas.hpp:631
constexpr std::size_t gemm_packed_threshold
Below this many multiply-adds the plain loop (gemm_rows, by blocks of rows held in registers) runs in...
Definition gemm.hpp:909
C complex_dot_product(const C *x, const C *y, std::size_t count)
Σ x[i] · y[i] of complex numbers: on the x86-64 units with AVX2 (the AVX-512 path too) their fused ch...
Definition gemm.hpp:753
bool on_release(void(*step)()) noexcept
Registers step among the calling thread's thread_releases, while a place is left (a workspace past th...
Definition buffer.hpp:65
void transpose_walk(std::size_t i0, std::size_t i1, std::size_t j0, std::size_t j1, std::size_t piece, const Copy &copy)
transpose_pieces of side piece (transpose_piece's 8 or the whole tile), each side its own instance: a...
Definition simd.hpp:142
void form_q_into(buffer< T > &out, const std::vector< reflector_block< T > > &blocks, std::size_t rows, std::size_t first, std::size_t count, bool transposed)
The columns [first, first + count) of Q = H₀ H₁ …, the blocks applied (the last first) to those of th...
T conjugate_dot_product(const T *x, const T *y, std::size_t count)
Σ conj(x[i]) · y[i], in order, where no native vector holds the parts.
Definition simd.hpp:1089
void gemm_at(std::size_t m, std::size_t n, std::size_t k, const T *at, std::size_t ldat, const T *b, std::size_t ldb, T *c, std::size_t ldc, c_start start=c_start::kept)
gemm_layouts with A given as Aᵀ (at, k × m, ldat apart).
Definition gemm.hpp:4787
void add_product(double *y, const double &f, const double *x, std::size_t count)
y[i] += f · x[i] for double, as subtract_product.
Definition gemm.hpp:648
void row_dots(const std::complex< double > *m, std::size_t ld, std::size_t rows, const std::complex< double > *x, std::size_t count, std::complex< double > *out)
row_dots for std::complex<double>, through complex_row_dots.
Definition gemm.hpp:802
void subtract_products(double *y, const double *f, const double *x, std::size_t ldx, std::size_t terms, std::size_t count)
y[i] -= Σₜ f[t] · x[(t · ldx) + i] for double, the units chosen as subtract_product chooses them,...
Definition gemm.hpp:522
T conj_of(const T &x)
The conjugate of a real (or general) scalar — the value itself.
constexpr std::size_t narrow_solve
The most right-hand sides an LU solve takes row by row rather than by blocks through the product kern...
void gemm_atbt(std::size_t m, std::size_t n, std::size_t k, const T *at, std::size_t ldat, const T *bt, std::size_t ldbt, T *c, std::size_t ldc, c_start start=c_start::kept)
gemm_layouts with both operands given as their transposes.
Definition gemm.hpp:4803
void gemm_bt(std::size_t m, std::size_t n, std::size_t k, const T *a, std::size_t lda, const T *bt, std::size_t ldbt, T *c, std::size_t ldc, c_start start=c_start::kept)
gemm_layouts with B given as Bᵀ (bt, n × k, ldbt apart).
Definition gemm.hpp:4771
magnitude_t< T > pivot_magnitude(const T &x)
The magnitude partial pivoting compares: |x| of a real x.
reflector_block< T > gather_reflectors(const std::vector< buffer< T > > &reflectors, std::size_t k0, std::size_t k1, std::size_t rows, const std::vector< T > *taus=nullptr)
Gathers the reflectors reflectors[k0…k1-1] (each I − τ_k v vᴴ: τ_k from taus, else 2 for a unit v; an...
void parallel_for(std::size_t count, std::size_t work_per_index, const Body &body)
Runs body(i) for every i in [0, count).
Definition parallel.hpp:790
std::size_t transpose_piece(std::size_t from_bytes, std::size_t to_bytes) noexcept
The side of the square pieces a transposing copy walks a tile by, from the bytes between rows of its ...
Definition simd.hpp:100
void gemm(std::size_t m, std::size_t n, std::size_t k, const T *a, std::size_t lda, const T *b, std::size_t ldb, T *c, std::size_t ldc, c_start start=c_start::kept)
C += A·B, every element of C summed in ascending order of the depth.
Definition gemm.hpp:4583
constexpr std::size_t qr_block
The reflectors of one panel of the blocked QR.
std::vector< reflector_block< T > > reflect_in_rows(buffer< T > &a, std::size_t rows, std::size_t cols, buffer< T > *r=nullptr, bool reflectors=true)
The blocks of reflectors of a Householder QR of the row-major a (rows × cols), factorised in place as...
constexpr std::size_t gemm_min_depth
Below this depth the plain loop runs too: each panel reads and writes its tiles of C once,...
Definition gemm.hpp:915
std::vector< reflector_block< T > > reflect_in_columns(buffer< T > &columns, std::size_t rows, std::size_t cols, bool reflectors=true)
The blocks of reflectors of a Householder QR of the column-major columns (rows per column,...
T chunked_dot(const T *a, const T *b, std::size_t count, const Dot &dot)
Σ a[i] · b[i] for a plain dot product: chunks of dot_chunk elements in parallel, each by dot,...
Definition gemm.hpp:5066
std::vector< T, detail::default_init_allocator< T > > buffer
The storage of vector, matrix and tensor, namely a std::vector whose buffer<T>(n) and resize(n) leave...
Definition buffer.hpp:443
T sum(const tensor< T > &t)
The sum of every element, by pairwise halving (0 for an empty tensor), on the threads where they are ...
tensor< T > diag(const tensor< T > &v, std::ptrdiff_t k)
The square matrix with the vector v on its k diagonal (above the main one for a positive k) and zeros...
least_squares_solution< T > least_squares(const matrix< T > &a, const matrix< T > &b, rank_cutoff cutoff={})
lstsq, with the residuals, the rank and the singular values numpy.linalg.lstsq returns beside the sol...
Definition svd.hpp:3031
@ amx
The Apple AMX coprocessor, fused multiply-adds; the products it does not suit on the NEON path's tile...
@ divide_and_conquer
Golub–Kahan bidiagonalisation then divide and conquer, as LAPACK's dgesdd: the default.
tensor< T > diagonal(const tensor< T > &t, std::ptrdiff_t offset)
The offset diagonal of each matrix of t (its last two axes), as numpy.linalg.diagonal: above the main...
vector< double > singular_values(const matrix< T > &a)
The singular values of a, descending, without its singular vectors, as numpy.linalg....
Definition svd.hpp:2274
vector< double > symmetric_eigenvalues(const matrix< T > &a)
The eigenvalues of the real symmetric or complex Hermitian a, ascending, without its eigenvectors,...
Definition svd.hpp:2328
A minimal std::thread parallel-for for the hot kernels.
The operands of syrk_triangle, which are row-major P = op(A) and Q = op(A)ᵀ (one of them scaled by α)...
Definition blas.hpp:727
std::size_t ldp
P's row distance.
Definition blas.hpp:729
bool q_is_pt
Q is Pᵀ read from P's rows (numerical::detail::gemm_bt), q unused.
Definition blas.hpp:736
const double * p
P, n × depth.
Definition blas.hpp:728
bool p_is_qt
P is Qᵀ read from Q's columns (numerical::detail::gemm_at), p unused.
Definition blas.hpp:737
const double * q
Q, depth × n.
Definition blas.hpp:730
std::size_t ldc
C's column distance.
Definition blas.hpp:734
std::size_t ldq
Q's row distance.
Definition blas.hpp:731
bool lower
The lower triangle (else the upper).
Definition blas.hpp:735
double * c
C, column-major.
Definition blas.hpp:733
The reflectors of one panel of the blocked QR, I − V T Vᴴ as LAPACK's dlarft forms it.
A least-squares solution and what numpy.linalg.lstsq reports beside it (least_squares).
Definition svd.hpp:3013
The pivoted LU factorisation of an m × n matrix (lu_factors): A = P L U.