Finish TODOs

3 files changed, 0 insertions, 445 deletions

diff --git a/experiments/hilbert_qr.cpp b/experiments/hilbert_qr.cpp
deleted file mode 100644
index 3a52194..0000000
--- a/experiments/hilbert_qr.cpp
+++ /dev/null
@@ -1,119 +0,0 @@
-import linalgebra;
-import std;
-
-using linalgebra::Matrix;
-using linalgebra::QRResult;
-
-Matrix hilbert(std::size_t n) {
-    Matrix H(n, n);
-    for (std::size_t i = 0; i < n; ++i)
-        for (std::size_t j = 0; j < n; ++j)
-            H(i, j) = 1.0 / static_cast<double>(i + j + 1);
-    return H;
-}
-
-double reconstruction_error(const Matrix& A, const QRResult& qr) {
-    const std::size_t m = A.rows();
-    const std::size_t n = A.cols();
-    const Matrix QR = qr.Q * qr.R;
-    double err = 0.0;
-    for (std::size_t i = 0; i < m; ++i)
-        for (std::size_t j = 0; j < n; ++j) {
-            const double d = A(i, j) - QR(i, j);
-            err += d * d;
-        }
-    return std::sqrt(err);
-}
-
-double orthogonality_error(const QRResult& qr) {
-    const Matrix& Q = qr.Q;
-    const std::size_t n = Q.cols();
-    double err = 0.0;
-    for (std::size_t i = 0; i < n; ++i)
-        for (std::size_t j = 0; j < n; ++j) {
-            double s = 0.0;
-            for (std::size_t k = 0; k < Q.rows(); ++k) s += Q(k, i) * Q(k, j);
-            const double d = s - (i == j ? 1.0 : 0.0);
-            err += d * d;
-        }
-    return std::sqrt(err);
-}
-
-using Clock = std::chrono::high_resolution_clock;
-using Seconds = std::chrono::duration<double>;
-
-template<typename Fn>
-double min_time(Fn fn, int trials = 5) {
-    double best = 1e18;
-    for (int t = 0; t < trials; ++t) {
-        const auto t0 = Clock::now();
-        fn();
-        const auto t1 = Clock::now();
-        best = std::min(best, Seconds(t1 - t0).count());
-    }
-    return best;
-}
-
-using QRFn = std::function<QRResult(const Matrix&)>;
-
-struct Result { double recon, ortho, time_s; };
-
-std::optional<Result> measure(const Matrix& A, QRFn fn) {
-    try {
-        const QRResult qr = fn(A);
-        const double re = reconstruction_error(A, qr);
-        const double oe = orthogonality_error(qr);
-        const double t = min_time([&] { fn(A); });
-        return Result{re, oe, t};
-    } catch (const std::exception&) {
-        return std::nullopt;
-    }
-}
-
-void print_row(const std::string& method, std::optional<Result> r) {
-    std::cout << std::left << std::setw(16) << method;
-    if (!r) {
-        std::cout << "  FAILED (linearly dependent columns)\n";
-        return;
-    }
-    std::cout << std::scientific << std::setprecision(2)
-              << std::setw(14) << r->recon
-              << std::setw(14) << r->ortho
-              << std::fixed << std::setprecision(3)
-              << std::setw(10) << r->time_s * 1e6 << " µs\n";
-}
-
-int main() {
-    std::cout << std::string(70, '*') << "\n";
-    std::cout << "  Hilbert QR Experiment: comparing GS variants and Householder\n";
-    std::cout << std::string(70, '*') << "\n\n";
-    std::cout <<
-        "H[i][j] = 1/(i+j+1). Condition number grows ~exponentially with n.\n"
-        "Orthogonality loss in classical GS tracks condition number directly.\n"
-        "Modified GS recovers ~half the lost digits. Householder is unaffected.\n\n";
-
-    const std::size_t sizes[] = {2, 3, 4, 5, 6, 7, 8, 10, 12};
-
-    for (std::size_t n : sizes) {
-        const Matrix H = hilbert(n);
-
-        std::cout << std::string(70, '-') << "\n";
-        std::cout << "  n = " << n << "\n";
-        std::cout << std::string(70, '-') << "\n";
-        std::cout << std::left
-                  << std::setw(16) << "Method"
-                  << std::setw(14) << "||A-QR||_F"
-                  << std::setw(14) << "||QtQ-I||_F"
-                  << std::setw(10) << "Time\n";
-        std::cout << std::string(70, ' ') << "\n";
-
-        print_row("classical_gs",
-            measure(H, [](const Matrix& A) { return linalgebra::qr_classical_gs(A); }));
-        print_row("modified_gs",
-            measure(H, [](const Matrix& A) { return linalgebra::qr_modified_gs(A); }));
-        print_row("householder",
-            measure(H, [](const Matrix& A) { return linalgebra::qr_householder(A); }));
-    }
-
-    return 0;
-}
diff --git a/experiments/matmul.cpp b/experiments/matmul.cpp
deleted file mode 100644
index a33b501..0000000
--- a/experiments/matmul.cpp
+++ /dev/null
@@ -1,130 +0,0 @@
-import linalgebra;
-import std;
-
-#if !defined(LINEAR_ALGEBRA_FORCE_SCALAR_MATMUL) && \
-      defined(__ARM_NEON) && defined(__aarch64__) && \
-      defined(__ARM_FEATURE_FP64_VECTOR_ARITHMETIC)
-#   define MATMUL_BACKEND "NEON"
-#else
-#   define MATMUL_BACKEND "scalar"
-#endif
-
-using linalgebra::Matrix;
-using Clock   = std::chrono::high_resolution_clock;
-using Seconds = std::chrono::duration<double>;
-
-
-Matrix naive_matmul(const Matrix& lhs, const Matrix& rhs) {
-    if (lhs.cols() != rhs.rows()) {
-        throw linalgebra::DimensionMismatchError(
-            "naive_matmul: lhs.cols() != rhs.rows()");
-    }
-    const std::size_t m = lhs.rows();
-    const std::size_t n = rhs.cols();
-    const std::size_t k = lhs.cols();
-
-    Matrix result(m, n, 0.0);
-
-    const double* A = lhs.data();
-    const double* B = rhs.data();
-    double*       C = result.data();
-
-    for (std::size_t i = 0; i < m; ++i)
-        for (std::size_t j = 0; j < n; ++j)
-            for (std::size_t p = 0; p < k; ++p)
-                C[i * n + j] += A[i * k + p] * B[p * n + j];
-
-    return result;
-}
-
-Matrix make_matrix(std::size_t n) {
-    Matrix M(n, n);
-    const double inv = 1.0 / static_cast<double>(n + 1);
-    for (std::size_t i = 0; i < n; ++i)
-        for (std::size_t j = 0; j < n; ++j)
-            M(i, j) = static_cast<double>(i + j + 1) * inv;
-    return M;
-}
-
-template <typename Fn>
-double min_time_s(Fn fn, int trials) {
-    double best = 1e30;
-    for (int t = 0; t < trials; ++t) {
-        const auto t0 = Clock::now();
-        fn();
-        const auto t1 = Clock::now();
-        const double elapsed = Seconds(t1 - t0).count();
-        if (elapsed < best) best = elapsed;
-    }
-    return best;
-}
-
-double flops(std::size_t n) {
-    const double nd = static_cast<double>(n);
-    return 2.0 * nd * nd * nd;
-}
-
-
-int main() {
-    const std::vector<std::size_t> sizes = {
-        8, 16, 32, 64, 128, 256, 512
-    };
-
-    constexpr std::size_t small_threshold = 128;
-    constexpr int         trials_small    = 9;
-    constexpr int         trials_large    = 3;
-
-    std::cout << std::string(72, '*') << "\n";
-    std::cout << "  Matmul benchmark: naive (ijk) vs SIMD (" MATMUL_BACKEND
-                 ") + transpose\n";
-    std::cout << "  C = A * B,  A and B both n×n\n";
-    std::cout << std::string(72, '*') << "\n\n";
-
-    std::cout << std::left
-              << std::setw(6)  << "n"
-              << std::setw(14) << "naive ms"
-              << std::setw(14) << "naive GFLOP/s"
-              << std::setw(14) << "SIMD ms"
-              << std::setw(14) << "SIMD GFLOP/s"
-              << std::setw(10) << "speedup"
-              << "\n";
-    std::cout << std::string(72, '-') << "\n";
-
-    for (const std::size_t n : sizes) {
-        const Matrix A = make_matrix(n);
-        const Matrix B = make_matrix(n);
-
-        const int trials = (n <= small_threshold) ? trials_small : trials_large;
-
-        volatile double sink_naive = naive_matmul(A, B)(0, 0);
-        volatile double sink_simd  = (A * B)(0, 0);
-        (void)sink_naive;
-        (void)sink_simd;
-
-        const double t_naive = min_time_s([&] { (void)naive_matmul(A, B); }, trials);
-        const double t_simd = min_time_s([&] { (void)(A * B); }, trials);
-
-        const double fp = flops(n);
-        const double gf_naive = fp / t_naive / 1e9;
-        const double gf_simd = fp / t_simd / 1e9;
-        const double speedup = t_naive / t_simd;
-
-        std::cout << std::left  << std::setw(6) << n
-                  << std::fixed << std::setprecision(3)
-                  << std::setw(14) << t_naive * 1e3
-                  << std::setprecision(2)
-                  << std::setw(14) << gf_naive
-                  << std::setprecision(3)
-                  << std::setw(14) << t_simd * 1e3
-                  << std::setprecision(2)
-                  << std::setw(14) << gf_simd
-                  << std::setprecision(2) << std::setw(10) << speedup
-                  << "x\n";
-    }
-
-    std::cout << "\n(each cell = minimum over "
-              << trials_small << " trials for n<=" << small_threshold
-              << ", " << trials_large << " trials for larger n)\n";
-
-    return 0;
-}
diff --git a/experiments/pivoting_vs_no_pivoting.cpp b/experiments/pivoting_vs_no_pivoting.cpp
deleted file mode 100644
index 2f043cb..0000000
--- a/experiments/pivoting_vs_no_pivoting.cpp
+++ /dev/null
@@ -1,196 +0,0 @@
-import linalgebra;
-import std;
-
-using linalgebra::Matrix;
-using linalgebra::Vector;
-
-struct NoPivotLU {
-    Matrix L;
-    Matrix U;
-    bool failed = false;
-    std::size_t fail_step = 0;
-};
-
-NoPivotLU lu_no_pivot(const Matrix& A, double tol = 1e-14) {
-    const std::size_t n = A.rows();
-    Matrix work = A;
-    Matrix L = Matrix::zeros(n, n);
-    for (std::size_t i = 0; i < n; ++i) L(i, i) = 1.0;
-    Matrix U = Matrix::zeros(n, n);
-
-    for (std::size_t k = 0; k < n; ++k) {
-        if (std::abs(work(k, k)) <= tol) {
-            return NoPivotLU{std::move(L), std::move(U), true, k};
-        }
-        for (std::size_t j = k; j < n; ++j) U(k, j) = work(k, j);
-        for (std::size_t i = k + 1; i < n; ++i) {
-            L(i, k) = work(i, k) / work(k, k);
-            for (std::size_t j = k + 1; j < n; ++j) {
-                work(i, j) -= L(i, k) * work(k, j);
-            }
-        }
-    }
-    return NoPivotLU{std::move(L), std::move(U), false, 0};
-}
-
-std::optional<Vector> solve_no_pivot(const NoPivotLU& f, const Vector& b) {
-    if (f.failed) return std::nullopt;
-    try {
-        const Vector y = linalgebra::forward_substitution(f.L, b, 1e-14, /*unit_diagonal=*/true);
-        return linalgebra::backward_substitution(f.U, y);
-    } catch (...) {
-        return std::nullopt;
-    }
-}
-
-double solve_residual(const Matrix& A, const Vector& x, const Vector& b) {
-    return linalgebra::norm2(A * x - b);
-}
-
-double reconstruction_error(const Matrix& A, const linalgebra::LUResult& lu) {
-    const std::size_t n = A.rows();
-    Matrix PA(n, n);
-    for (std::size_t i = 0; i < n; ++i)
-        for (std::size_t j = 0; j < n; ++j)
-            PA(i, j) = A(lu.perm[i], j);
-    const Matrix LU_prod = lu.L * lu.U;
-    double err = 0.0;
-    for (std::size_t i = 0; i < n; ++i)
-        for (std::size_t j = 0; j < n; ++j) {
-            const double d = PA(i, j) - LU_prod(i, j);
-            err += d * d;
-        }
-    return std::sqrt(err);
-}
-
-void print_header(const std::string& title) {
-    std::cout << "\n" << std::string(60, '=') << "\n";
-    std::cout << "  " << title << "\n";
-    std::cout << std::string(60, '=') << "\n";
-    std::cout << std::left
-              << std::setw(22) << "Method"
-              << std::setw(20) << "||Ax - b||"
-              << std::setw(20) << "||PA - LU||"
-              << "\n";
-    std::cout << std::string(60, '-') << "\n";
-}
-
-void report_pivoted(const Matrix& A, const Vector& b) {
-    try {
-        const linalgebra::LUResult lu = linalgebra::lu_factor(A);
-        const Vector x = linalgebra::lu_solve(lu, b);
-        std::cout << std::left << std::setw(22) << "Pivoted LU"
-                  << std::setw(20) << std::scientific << std::setprecision(3)
-                  << solve_residual(A, x, b)
-                  << std::setw(20) << reconstruction_error(A, lu)
-                  << "\n";
-    } catch (const std::exception& e) {
-        std::cout << std::left << std::setw(22) << "Pivoted LU"
-                  << "FAILED: " << e.what() << "\n";
-    }
-}
-
-void report_no_pivot(const Matrix& A, const Vector& b) {
-    const NoPivotLU f = lu_no_pivot(A);
-    if (f.failed) {
-        std::cout << std::left << std::setw(22) << "No-pivot LU"
-                  << "FAILED at step " << f.fail_step << " (zero pivot)\n";
-        return;
-    }
-    const auto x_opt = solve_no_pivot(f, b);
-    if (!x_opt) {
-        std::cout << std::left << std::setw(22) << "No-pivot LU"
-                  << "FAILED during solve (singular U)\n";
-        return;
-    }
-    const Matrix LU_prod = f.L * f.U;
-    double rec_err = 0.0;
-    for (std::size_t i = 0; i < A.rows(); ++i)
-        for (std::size_t j = 0; j < A.cols(); ++j) {
-            const double d = A(i, j) - LU_prod(i, j);
-            rec_err += d * d;
-        }
-    rec_err = std::sqrt(rec_err);
-
-    std::cout << std::left << std::setw(22) << "No-pivot LU"
-              << std::setw(20) << std::scientific << std::setprecision(3)
-              << solve_residual(A, *x_opt, b)
-              << std::setw(20) << rec_err
-              << "\n";
-}
-
-void run_case(const std::string& label, const Matrix& A, const Vector& b) {
-    print_header(label);
-    report_pivoted(A, b);
-    report_no_pivot(A, b);
-}
-
-void exp_random(std::size_t n = 8) {
-    std::mt19937 rng(42);
-    std::uniform_real_distribution<double> dist(-5.0, 5.0);
-    Matrix A(n, n);
-    for (std::size_t i = 0; i < n; ++i)
-        for (std::size_t j = 0; j < n; ++j)
-            A(i, j) = dist(rng);
-
-    Vector b(n);
-    for (std::size_t i = 0; i < n; ++i) b[i] = dist(rng);
-
-    run_case("Random 8x8 (well-conditioned)", A, b);
-}
-
-void exp_badly_scaled() {
-    const Matrix A{
-        {1e-14, 1.0,   2.0  },
-        {1.0,   3.0,   4.0  },
-        {2.0,   5.0,   7.0  }
-    };
-    const Vector b{1e-14 + 3.0, 8.0, 14.0};
-    run_case("Badly scaled (row norms differ by 10^14)", A, b);
-}
-
-void exp_epsilon_pathology() {
-    constexpr double eps = 1e-15;
-    const Matrix A{{eps, 1.0}, {1.0, 2.0}};
-    const Vector b{1.0 + eps, 3.0};
-    run_case("Epsilon pathology [[1e-15,1],[1,2]] (classic)", A, b);
-    std::cout << "  Note: exact solution is x = [1, 1]\n";
-}
-
-void exp_amplified_multiplier() {
-    const Matrix A{
-        {0.001, 1.0,   0.0,   0.0  },
-        {1.0,   2.0,   1.0,   0.0  },
-        {0.0,   1.0,   3.0,   1.0  },
-        {0.0,   0.0,   1.0,   4.0  }
-    };
-    const Vector b = A * Vector{1.0, 2.0, 3.0, 4.0};
-    run_case("Amplified multiplier (small (1,1) pivot, 4x4)", A, b);
-    std::cout << "  Note: exact solution is x = [1, 2, 3, 4]\n";
-}
-
-void exp_permutation() {
-    const Matrix A{
-        {0.0, 0.0, 3.0},
-        {0.0, 2.0, 1.0},
-        {5.0, 1.0, 0.0}
-    };
-    const Vector b = A * Vector{1.0, -1.0, 2.0};
-    run_case("Multiple row swaps required (zeros in pivot positions)", A, b);
-}
-
-int main() {
-    std::cout << std::string(60, '*') << "\n";
-    std::cout << "  Pivoting vs No-Pivoting LU Experiment\n";
-    std::cout << std::string(60, '*') << "\n";
-    std::cout << "Residual  = ||Ax - b||_2   (solve accuracy)\n";
-    std::cout << "Recon err = ||PA - LU||_F  (factorization accuracy)\n";
-
-    exp_random();
-    exp_badly_scaled();
-    exp_epsilon_pathology();
-    exp_amplified_multiplier();
-    exp_permutation();
-
-    return 0;
-}