QuantLib: a free/open-source library for quantitative finance
fully annotated source code - version 1.34
Loading...
Searching...
No Matches
qrdecomposition.cpp
Go to the documentation of this file.
1/* -*- mode: c++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2
3/*
4 Copyright (C) 2008 Klaus Spanderen
5
6 This file is part of QuantLib, a free-software/open-source library
7 for financial quantitative analysts and developers - http://quantlib.org/
8
9 QuantLib is free software: you can redistribute it and/or modify it
10 under the terms of the QuantLib license. You should have received a
11 copy of the license along with this program; if not, please email
12 <quantlib-dev@lists.sf.net>. The license is also available online at
13 <http://quantlib.org/license.shtml>.
14
15 This program is distributed in the hope that it will be useful, but WITHOUT
16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17 FOR A PARTICULAR PURPOSE. See the license for more details.
18*/
19
20/*! \file qrdecomposition.cpp
21 \brief QR decomposition
22*/
23
26#include <memory>
27
28namespace QuantLib {
29
30 std::vector<Size> qrDecomposition(const Matrix& M,
31 Matrix& q,
32 Matrix& r,
33 bool pivot) {
34 Matrix mT = transpose(M);
35 const Size m = M.rows();
36 const Size n = M.columns();
37
38 std::unique_ptr<int[]> lipvt(new int[n]);
39 std::unique_ptr<Real[]> rdiag(new Real[n]);
40 std::unique_ptr<Real[]> wa(new Real[n]);
41
42 MINPACK::qrfac(m, n, mT.begin(), 0, (pivot)?1:0,
43 lipvt.get(), n, rdiag.get(), rdiag.get(), wa.get());
44 if (r.columns() != n || r.rows() !=n)
45 r = Matrix(n, n);
46
47 for (Size i=0; i < n; ++i) {
48 std::fill(r.row_begin(i), r.row_begin(i)+i, 0.0);
49 r[i][i] = rdiag[i];
50 if (i < m) {
51 std::copy(mT.column_begin(i)+i+1, mT.column_end(i),
52 r.row_begin(i)+i+1);
53 }
54 else {
55 std::fill(r.row_begin(i)+i+1, r.row_end(i), 0.0);
56 }
57 }
58
59 if (q.rows() != m || q.columns() != n)
60 q = Matrix(m, n);
61
62 if (m > n) {
63 std::fill(q.begin(), q.end(), 0.0);
64
65 Integer u = std::min(n,m);
66 for (Integer i=0; i < u; ++i)
67 q[i][i] = 1.0;
68
69 Array v(m);
70 for (Integer i=u-1; i >=0; --i) {
71 if (std::fabs(mT[i][i]) > QL_EPSILON) {
72 const Real tau = 1.0/mT[i][i];
73
74 std::fill(v.begin(), v.begin()+i, 0.0);
75 std::copy(mT.row_begin(i)+i, mT.row_end(i), v.begin()+i);
76
77 Array w(n, 0.0);
78 for (Size l=0; l < n; ++l)
79 w[l] += std::inner_product(
80 v.begin()+i, v.end(), q.column_begin(l)+i, Real(0.0));
81
82 for (Size k=i; k < m; ++k) {
83 const Real a = tau*v[k];
84 for (Size l=0; l < n; ++l)
85 q[k][l] -= a*w[l];
86 }
87 }
88 }
89 }
90 else {
91 Array w(m);
92 for (Size k=0; k < m; ++k) {
93 std::fill(w.begin(), w.end(), 0.0);
94 w[k] = 1.0;
95
96 for (Size j=0; j < std::min(n, m); ++j) {
97 const Real t3 = mT[j][j];
98 if (t3 != 0.0) {
99 const Real t
100 = std::inner_product(mT.row_begin(j)+j, mT.row_end(j),
101 w.begin()+j, Real(0.0))/t3;
102 for (Size i=j; i<m; ++i) {
103 w[i]-=mT[j][i]*t;
104 }
105 }
106 q[k][j] = w[j];
107 }
108 std::fill(q.row_begin(k) + std::min(n, m), q.row_end(k), 0.0);
109 }
110 }
111
112 std::vector<Size> ipvt(n);
113
114 if (pivot) {
115 std::copy(lipvt.get(), lipvt.get()+n, ipvt.begin());
116 }
117 else {
118 for (Size i=0; i < n; ++i)
119 ipvt[i] = i;
120 }
121
122 return ipvt;
123 }
124
125 Array qrSolve(const Matrix& a, const Array& b,
126 bool pivot, const Array& d) {
127 const Size m = a.rows();
128 const Size n = a.columns();
129
130 QL_REQUIRE(b.size() == m, "dimensions of A and b don't match");
131 QL_REQUIRE(d.size() == n || d.empty(),
132 "dimensions of A and d don't match");
133
134 Matrix q(m, n), r(n, n);
135
136 std::vector<Size> lipvt = qrDecomposition(a, q, r, pivot);
137
138 std::unique_ptr<int[]> ipvt(new int[n]);
139 std::copy(lipvt.begin(), lipvt.end(), ipvt.get());
140
141 Matrix rT = transpose(r);
142
143 std::unique_ptr<Real[]> sdiag(new Real[n]);
144 std::unique_ptr<Real[]> wa(new Real[n]);
145
146 Array ld(n, 0.0);
147 if (!d.empty()) {
148 std::copy(d.begin(), d.end(), ld.begin());
149 }
150
151 Array x(n);
152 Array qtb = transpose(q)*b;
153
154 MINPACK::qrsolv(n, rT.begin(), n, ipvt.get(),
155 ld.begin(), qtb.begin(),
156 x.begin(), sdiag.get(), wa.get());
157
158 return x;
159 }
160}
1-D array used in linear algebra.
Definition: array.hpp:52
const_iterator end() const
Definition: array.hpp:511
const_iterator begin() const
Definition: array.hpp:503
Matrix used in linear algebra.
Definition: matrix.hpp:41
const_row_iterator row_begin(Size i) const
Definition: matrix.hpp:360
const_iterator begin() const
Definition: matrix.hpp:327
Size rows() const
Definition: matrix.hpp:504
Size columns() const
Definition: matrix.hpp:508
const_column_iterator column_begin(Size i) const
Definition: matrix.hpp:415
const_row_iterator row_end(Size i) const
Definition: matrix.hpp:378
const_column_iterator column_end(Size i) const
Definition: matrix.hpp:434
const DefaultType & t
#define QL_REQUIRE(condition, message)
throw an error if the given pre-condition is not verified
Definition: errors.hpp:117
Date d
ext::function< Real(Real)> b
#define QL_EPSILON
Definition: qldefines.hpp:178
QL_REAL Real
real number
Definition: types.hpp:50
QL_INTEGER Integer
integer number
Definition: types.hpp:35
std::size_t Size
size of a container
Definition: types.hpp:58
wrapper for MINPACK minimization routine
void qrfac(int m, int n, Real *a, int, int pivot, int *ipvt, int, Real *rdiag, Real *acnorm, Real *wa)
Definition: lmdif.cpp:374
void qrsolv(int n, Real *r, int ldr, const int *ipvt, const Real *diag, const Real *qtb, Real *x, Real *sdiag, Real *wa)
Definition: lmdif.cpp:580
Definition: any.hpp:35
Array qrSolve(const Matrix &a, const Array &b, bool pivot, const Array &d)
QR Solve.
std::vector< Size > qrDecomposition(const Matrix &M, Matrix &q, Matrix &r, bool pivot)
QR decompoisition.
Matrix transpose(const Matrix &m)
Definition: matrix.hpp:700
ext::shared_ptr< YieldTermStructure > q
ext::shared_ptr< YieldTermStructure > r
ext::shared_ptr< BlackVolTermStructure > v
QR decomposition.