Gaussian elimination
(Mylib/LinearAlgebra/gaussian_elimination.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

References

Verified with

• test/aoj/1300/main.test.cpp

Code

#pragma once
#include <utility>
#include <vector>

namespace haar_lib {
  template <typename T>
  int gaussian_elimination(std::vector<std::vector<T>> &a) {
    const int h = a.size();
    const int w = a[0].size();
    int rank    = 0;

    for (int j = 0; j < w; ++j) {
      int pivot = -1;

      for (int i = rank; i < h; ++i) {
        if (a[i][j] != 0) {
          pivot = i;
          break;
        }
      }

      if (pivot == -1) continue;

      std::swap(a[pivot], a[rank]);

      auto d = a[rank][j];
      for (int k = 0; k < w; ++k) a[rank][k] /= d;

      for (int i = 0; i < h; ++i) {
        if (i == rank or a[i][j] == 0) continue;
        auto d = a[i][j];
        for (int k = 0; k < w; ++k) {
          a[i][k] -= a[rank][k] * d;
        }
      }

      ++rank;
    }

    return rank;
  }
}  // namespace haar_lib

#line 2 "Mylib/LinearAlgebra/gaussian_elimination.cpp"
#include <utility>
#include <vector>

namespace haar_lib {
  template <typename T>
  int gaussian_elimination(std::vector<std::vector<T>> &a) {
    const int h = a.size();
    const int w = a[0].size();
    int rank    = 0;

    for (int j = 0; j < w; ++j) {
      int pivot = -1;

      for (int i = rank; i < h; ++i) {
        if (a[i][j] != 0) {
          pivot = i;
          break;
        }
      }

      if (pivot == -1) continue;

      std::swap(a[pivot], a[rank]);

      auto d = a[rank][j];
      for (int k = 0; k < w; ++k) a[rank][k] /= d;

      for (int i = 0; i < h; ++i) {
        if (i == rank or a[i][j] == 0) continue;
        auto d = a[i][j];
        for (int k = 0; k < w; ++k) {
          a[i][k] -= a[rank][k] * d;
        }
      }

      ++rank;
    }

    return rank;
  }
}  // namespace haar_lib

Back to top page