TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
qr_decomposition.cpp File Reference

Program to compute the QR decomposition of a given matrix. More...

#include <array>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include "./qr_decompose.h"
Include dependency graph for qr_decomposition.cpp:

Go to the source code of this file.

Functions

int main (void)
 
template<typename T>
void qr_decompose (const std::valarray< std::valarray< T > > &A, std::valarray< std::valarray< T > > *Q, std::valarray< std::valarray< T > > *R)
 
template<typename T>
std::ostream & operator<< (std::ostream &out, std::valarray< std::valarray< T > > const &v)
 

Detailed Description

Program to compute the QR decomposition of a given matrix.

Author
Krishna Vedala

Definition in file qr_decomposition.cpp.

Function Documentation

◆ main()

int main ( void )

main function

Definition at line 23 of file qr_decomposition.cpp.

23 {
24 unsigned int ROWS, COLUMNS;
25
26 std::cout << "Enter the number of rows and columns: ";
27 std::cin >> ROWS >> COLUMNS;
28
29 std::cout << "Enter matrix elements row-wise:\n";
30
31 std::valarray<std::valarray<double>> A(ROWS);
32 std::valarray<std::valarray<double>> Q(ROWS);
33 std::valarray<std::valarray<double>> R(COLUMNS);
34 for (int i = 0; i < std::max(ROWS, COLUMNS); i++) {
35 if (i < ROWS) {
36 A[i] = std::valarray<double>(COLUMNS);
37 Q[i] = std::valarray<double>(COLUMNS);
38 }
39 if (i < COLUMNS) {
40 R[i] = std::valarray<double>(COLUMNS);
41 }
42 }
43
44 for (int i = 0; i < ROWS; i++)
45 for (int j = 0; j < COLUMNS; j++) std::cin >> A[i][j];
46
47 std::cout << A << "\n";
48
49 clock_t t1 = clock();
50 qr_decompose(A, &Q, &R);
51 double dtime = static_cast<double>(clock() - t1) / CLOCKS_PER_SEC;
52
53 std::cout << Q << "\n";
54 std::cout << R << "\n";
55 std::cout << "Time taken to compute: " << dtime << " sec\n ";
56
57 return 0;
58}
void qr_decompose(const std::valarray< std::valarray< T > > &A, std::valarray< std::valarray< T > > *Q, std::valarray< std::valarray< T > > *R)

◆ operator<<()

template<typename T>
std::ostream & qr_algorithm::operator<< ( std::ostream & out,
std::valarray< std::valarray< T > > const & v )

operator to print a matrix

Definition at line 33 of file qr_decompose.h.

34 {
35 const int width = 12;
36 const char separator = ' ';
37
38 out.precision(4);
39 for (size_t row = 0; row < v.size(); row++) {
40 for (size_t col = 0; col < v[row].size(); col++)
41 out << std::right << std::setw(width) << std::setfill(separator)
42 << v[row][col];
43 out << std::endl;
44 }
45
46 return out;
47}

◆ qr_decompose()

template<typename T>
void qr_algorithm::qr_decompose ( const std::valarray< std::valarray< T > > & A,
std::valarray< std::valarray< T > > * Q,
std::valarray< std::valarray< T > > * R )

Decompose matrix \(A\) using Gram-Schmidt process.

\begin{eqnarray*} \text{given that}\quad A &=& *\left[\mathbf{a}_1,\mathbf{a}_2,\ldots,\mathbf{a}_{N-1},\right]\\ \text{where}\quad\mathbf{a}_i &=& \left[a_{0i},a_{1i},a_{2i},\ldots,a_{(M-1)i}\right]^T\quad\ldots\mbox{(column vectors)}\\ \text{then}\quad\mathbf{u}_i &=& \mathbf{a}_i *-\sum_{j=0}^{i-1}\text{proj}_{\mathbf{u}_j}\mathbf{a}_i\\ \mathbf{e}_i &=&\frac{\mathbf{u}_i}{\left|\mathbf{u}_i\right|}\\ Q &=& \begin{bmatrix}\mathbf{e}_0 & \mathbf{e}_1 & \mathbf{e}_2 & \dots & \mathbf{e}_{N-1}\end{bmatrix}\\ R &=& \begin{bmatrix}\langle\mathbf{e}_0\,,\mathbf{a}_0\rangle & \langle\mathbf{e}_1\,,\mathbf{a}_1\rangle & \langle\mathbf{e}_2\,,\mathbf{a}_2\rangle & \dots \\ 0 & \langle\mathbf{e}_1\,,\mathbf{a}_1\rangle & \langle\mathbf{e}_2\,,\mathbf{a}_2\rangle & \dots\\ 0 & 0 & \langle\mathbf{e}_2\,,\mathbf{a}_2\rangle & \dots\\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}\\ \end{eqnarray*}

Parameters
Ainput matrix to decompose
Qoutput decomposed matrix
Routput decomposed matrix

Definition at line 146 of file qr_decompose.h.

150 {
151 std::size_t ROWS = A.size(); // number of rows of A
152 std::size_t COLUMNS = A[0].size(); // number of columns of A
153 std::valarray<T> col_vector(ROWS);
154 std::valarray<T> col_vector2(ROWS);
155 std::valarray<T> tmp_vector(ROWS);
156
157 for (int i = 0; i < COLUMNS; i++) {
158 /* for each column => R is a square matrix of NxN */
159 int j;
160 R[0][i] = 0.; /* make R upper triangular */
161
162 /* get corresponding Q vector */
163#ifdef _OPENMP
164// parallelize on threads
165#pragma omp for
166#endif
167 for (j = 0; j < ROWS; j++) {
168 tmp_vector[j] = A[j][i]; /* accumulator for uk */
169 col_vector[j] = A[j][i];
170 }
171 for (j = 0; j < i; j++) {
172 for (int k = 0; k < ROWS; k++) {
173 col_vector2[k] = Q[0][k][j];
174 }
175 col_vector2 = vector_proj(col_vector, col_vector2);
176 tmp_vector -= col_vector2;
177 }
178
179 double mag = vector_mag(tmp_vector);
180
181#ifdef _OPENMP
182// parallelize on threads
183#pragma omp for
184#endif
185 for (j = 0; j < ROWS; j++) Q[0][j][i] = tmp_vector[j] / mag;
186
187 /* compute upper triangular values of R */
188#ifdef _OPENMP
189// parallelize on threads
190#pragma omp for
191#endif
192 for (int kk = 0; kk < ROWS; kk++) {
193 col_vector[kk] = Q[0][kk][i];
194 }
195
196#ifdef _OPENMP
197// parallelize on threads
198#pragma omp for
199#endif
200 for (int k = i; k < COLUMNS; k++) {
201 for (int kk = 0; kk < ROWS; kk++) {
202 col_vector2[kk] = A[kk][k];
203 }
204 R[0][i][k] = (col_vector * col_vector2).sum();
205 }
206 }
207}
double k(double x)
Another test function.
T sum(const std::vector< std::valarray< T > > &A)
std::valarray< T > vector_proj(const std::valarray< T > &a, const std::valarray< T > &b)
double vector_mag(const std::valarray< T > &a)
double mag(const std::array< double, 3 > &vec)
Calculates the magnitude of the mathematical vector from it's direction ratios.