aboutsummaryrefslogtreecommitdiff
path: root/experiments
diff options
context:
space:
mode:
Diffstat (limited to 'experiments')
-rw-r--r--experiments/hilbert_qr.cpp119
-rw-r--r--experiments/matmul.cpp130
-rw-r--r--experiments/pivoting_vs_no_pivoting.cpp196
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;
-}
generated by cgit v1.2.3 (git 2.51.0) at 2026-09-01 21:32:44 +0000