Dukales

determinant based on LUP-decomposition

Oct 30th, 2015
230
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.38 KB | None | 0 0
  1. #include <valarray>
  2. #include <vector>
  3. #include <utility>
  4.  
  5. #include <cmath>
  6. #include <cstddef>
  7. #include <cassert>
  8.  
  9. template< typename value_type >
  10. struct math
  11. {
  12.  
  13.     using size_type = std::size_t;
  14.    
  15.     size_type const dimension_;
  16.     value_type const & eps;
  17.    
  18.     value_type const zero = value_type(0);
  19.     value_type const one = value_type(1);
  20.    
  21. private :
  22.    
  23.     using vector = std::valarray< value_type >;
  24.     using matrix = std::vector< vector >;
  25.  
  26.     matrix matrix_;
  27.    
  28.     value_type
  29.     det(matrix & _matrix,
  30.         size_type const _dimension) // hottest function
  31.     { // calculates lower unit triangular matrix and upper triangular
  32.         assert(0 < _dimension);
  33.         value_type det_ = one;
  34.         for (size_type i = 0; i < _dimension; ++i) {
  35.             vector & mi_ = _matrix[i];
  36.             size_type pivot = i;
  37.             {
  38.                 using std::abs;
  39.                 value_type max_ = abs(mi_[i]);
  40.                 size_type j = i;
  41.                 while (++j < _dimension) {
  42.                     value_type y_ = abs(_matrix[j][i]);
  43.                     if (max_ < y_) {
  44.                         max_ = std::move(y_);
  45.                         pivot = j;
  46.                     }
  47.                 }
  48.                 if (!(eps < max_)) { // regular?
  49.                     return zero; // singular
  50.                 }
  51.             }
  52.             if (pivot != i) {
  53.                 det_ = -det_; // each permutation flips sign of det
  54.                 mi_.swap(_matrix[pivot]);
  55.             }
  56.             value_type const & dia_ = mi_[i];
  57.             det_ *= dia_; // det is multiple of diagonal elements
  58.             size_type j = i;
  59.             while (++j < _dimension) {
  60.                 vector & mj_ = _matrix[j];
  61.                 value_type & mji_ = mj_[i];
  62.                 mji_ /= dia_;
  63.                 size_type k = i;
  64.                 while (++k < _dimension) {
  65.                     mj_[k] -= mji_ * mi_[k];
  66.                 }
  67.             }
  68.         }
  69.         return det_;
  70.     }
  71.    
  72. public :
  73.  
  74.     math(size_type const _dimension,
  75.          value_type const & _eps)
  76.         : dimension_(_dimension)
  77.         , eps(_eps)
  78.         , matrix_(dimension_)
  79.     {
  80.         assert(1 < dimension_);
  81.         assert(!(eps < zero));
  82.         for (size_type r = 0; r < dimension_; ++r) {
  83.             matrix_[r].resize(dimension_);
  84.         }
  85.     }
  86.    
  87.     template< typename rhs = matrix >
  88.     void
  89.     operator = (rhs const & _matrix)
  90.     {
  91.         auto irow = std::begin(matrix_);
  92.         for (auto const & row_ : _matrix) {
  93.             auto icol = std::begin(*irow);
  94.             for (auto const & v : row_) {
  95.                 *icol = v;
  96.                 ++icol;
  97.             }
  98.             ++irow;
  99.         }
  100.     }
  101.  
  102.     value_type
  103.     det()
  104.     {
  105.         return det(matrix_, dimension_);
  106.     }
  107.    
  108. };
  109.  
  110. // main.cpp
  111. #include <iostream>
  112.  
  113. #include <cstdlib>
  114.  
  115. int
  116. main()
  117. {
  118.     using value_type = double;
  119.     value_type const eps = std::numeric_limits< value_type >::epsilon();
  120.     std::size_t const dimension_ = 3;
  121.     math< value_type > m(dimension_, eps);
  122.     m = { // example from https://en.wikipedia.org/wiki/Determinant#Laplace.27s_formula_and_the_adjugate_matrix
  123.             {-2.0, 2.0, -3.0},
  124.             {-1.0, 1.0,  3.0},
  125.             { 2.0, 0.0, -1.0}
  126.         };
  127.     std::cout << m.det() << std::endl; // 18
  128.     return EXIT_SUCCESS;
  129. }
Advertisement
Add Comment
Please, Sign In to add comment