Stokhos Package Browser (Single Doxygen Collection) Version of the Day
Loading...
Searching...
No Matches
Stokhos_Lanczos.hpp
Go to the documentation of this file.
1// @HEADER
2// ***********************************************************************
3//
4// Stokhos Package
5// Copyright (2009) Sandia Corporation
6//
7// Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
8// license for use of this work by or on behalf of the U.S. Government.
9//
10// Redistribution and use in source and binary forms, with or without
11// modification, are permitted provided that the following conditions are
12// met:
13//
14// 1. Redistributions of source code must retain the above copyright
15// notice, this list of conditions and the following disclaimer.
16//
17// 2. Redistributions in binary form must reproduce the above copyright
18// notice, this list of conditions and the following disclaimer in the
19// documentation and/or other materials provided with the distribution.
20//
21// 3. Neither the name of the Corporation nor the names of the
22// contributors may be used to endorse or promote products derived from
23// this software without specific prior written permission.
24//
25// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36//
37// Questions? Contact Eric T. Phipps (etphipp@sandia.gov).
38//
39// ***********************************************************************
40// @HEADER
41
42#ifndef STOKHOS_LANCZOS_HPP
43#define STOKHOS_LANCZOS_HPP
44
45#include "Teuchos_Array.hpp"
46#include "Teuchos_SerialDenseVector.hpp"
47#include "Teuchos_SerialDenseMatrix.hpp"
48#include "Teuchos_SerialDenseHelpers.hpp"
49
50namespace Stokhos {
51
52 template <typename ord_type, typename val_type>
54 public:
55 typedef ord_type ordinal_type;
56 typedef val_type value_type;
57 typedef Teuchos::SerialDenseVector<ordinal_type, value_type> vector_type;
58
60 w(weights),
61 n(weights.length())
62 {
63 }
64
66
68
70 inner_product(const vector_type& u, const vector_type& v) const {
72 for (ordinal_type j=0; j<n; j++)
73 val += w[j]*u[j]*v[j];
74 return val;
75 }
76
77 void
78 add2(const value_type& a, const vector_type& u1,
79 const value_type& b, const vector_type& u2, vector_type& v) const {
80 for (ordinal_type j=0; j<n; j++)
81 v[j] = a*u1[j] + b*u2[j];
82 }
83
84 void
85 add3(const value_type& a, const vector_type& u1,
86 const value_type& b, const vector_type& u2,
87 const value_type& c, const vector_type& u3, vector_type& v) const {
88 for (ordinal_type j=0; j<n; j++)
89 v[j] = a*u1[j] + b*u2[j] +c*u3[j];
90 }
91
92 protected:
93
94 const vector_type& w;
96
97 };
98
120 template <typename vectorspace_type, typename operator_type>
121 class Lanczos {
122 public:
123
124 typedef typename operator_type::ordinal_type ordinal_type;
125 typedef typename operator_type::value_type value_type;
126 typedef Teuchos::SerialDenseVector<ordinal_type,value_type> vector_type;
127 typedef Teuchos::SerialDenseMatrix<ordinal_type,value_type> matrix_type;
128
130 static void compute(ordinal_type k,
131 const vectorspace_type& vs,
132 const operator_type& A,
133 const vector_type& u_init,
134 matrix_type& u,
135 Teuchos::Array<value_type>& alpha,
136 Teuchos::Array<value_type>& beta,
137 Teuchos::Array<value_type>& nrm_sqrd) {
138 beta[0] = 1.0;
139
140 // u[i-1], u[i], u[i+1]
141 vector_type u0, u1, u2;
142
143 // set starting vector
144 u0 = Teuchos::getCol(Teuchos::View, u, 0);
145 u0.assign(u_init);
146 u1 = u0;
147
148 value_type nrm;
149 vector_type v = vs.create_vector();
150 for (ordinal_type i=0; i<k; i++) {
151
152 // Compute (u_i,u_i)
153 nrm_sqrd[i] = vs.inner_product(u1, u1);
154
155 // Compute v = A*u_i
156 A.apply(u1, v);
157
158 // Compute (v,u_i)
159 nrm = vs.inner_product(u1, v);
160
161 // Compute alpha = (v,u_i) / (u_i,u_i)
162 alpha[i] = nrm / nrm_sqrd[i];
163
164 // Compute beta = (u_i,u_i) / (u_{i-1}.u_{i-1})
165 if (i > 0)
166 beta[i] = nrm_sqrd[i] / nrm_sqrd[i-1];
167
168 // Compute u_{i+1} = v - alpha_i*u_i - beta_i*u_{i-1}
169 if (i < k-1) {
170 u2 = Teuchos::getCol(Teuchos::View, u, i+1);
171 if (i == 0)
172 vs.add2(value_type(1), v, -alpha[i], u1, u2);
173 else
174 vs.add3(value_type(1), v, -alpha[i], u1, -beta[i], u0, u2);
175 gramSchmidt(i+1, vs, u, u2);
176 }
177
178 // std::cout << "i = " << i
179 // << " alpha = " << alpha[i] << " beta = " << beta[i]
180 // << " nrm = " << nrm_sqrd[i] << std::endl;
181 TEUCHOS_TEST_FOR_EXCEPTION(nrm_sqrd[i] < 0, std::logic_error,
182 "Stokhos::LanczosProjPCEBasis::lanczos(): "
183 << " Polynomial " << i << " out of " << k
184 << " has norm " << nrm_sqrd[i] << "!");
185
186 // Shift -- these are just pointer copies
187 u0 = u1;
188 u1 = u2;
189
190 }
191 }
192
195 const vectorspace_type& vs,
196 const operator_type& A,
197 const vector_type& u_init,
198 matrix_type& u,
199 Teuchos::Array<value_type>& alpha,
200 Teuchos::Array<value_type>& beta,
201 Teuchos::Array<value_type>& nrm_sqrd) {
202
203 // u[i-1], u[i], u[i+1]
204 vector_type u0, u1, u2;
205
206 // set starting vector
207 u0 = Teuchos::getCol(Teuchos::View, u, 0);
208 u0.assign(u_init);
209 u1 = u0;
210
211 vector_type v = vs.create_vector();
212 for (ordinal_type i=0; i<k; i++) {
213
214 // Compute (u_i,u_i)
215 beta[i] = std::sqrt(vs.inner_product(u1, u1));
216 u1.scale(1.0/beta[i]);
217 nrm_sqrd[i] = value_type(1.0);
218
219 // Compute v = A*u_i
220 A.apply(u1, v);
221
222 // Compute (v,u_i)
223 alpha[i] = vs.inner_product(u1, v);
224
225 // Compute u_{i+1} = v - alpha_i*u_i - beta_i*u_{i-1}
226 if (i < k-1) {
227 u2 = Teuchos::getCol(Teuchos::View, u, i+1);
228 if (i == 0)
229 vs.add2(value_type(1), v, -alpha[i], u1, u2);
230 else
231 vs.add3(value_type(1), v, -alpha[i], u1, -beta[i], u0, u2);
232 gramSchmidt(i+1, vs, u, u2);
233 }
234
235 // std::cout << "i = " << i
236 // << " alpha = " << alpha[i] << " beta = " << beta[i]
237 // << " nrm = " << nrm_sqrd[i] << std::endl;
238 TEUCHOS_TEST_FOR_EXCEPTION(nrm_sqrd[i] < 0, std::logic_error,
239 "Stokhos::LanczosProjPCEBasis::lanczos(): "
240 << " Polynomial " << i << " out of " << k
241 << " has norm " << nrm_sqrd[i] << "!");
242
243 // Shift -- these are just pointer copies
244 u0 = u1;
245 u1 = u2;
246
247 }
248 }
249
251 static void gramSchmidt(ordinal_type k, const vectorspace_type& vs,
252 matrix_type& u, vector_type& u2) {
253 vector_type u0;
254 value_type nrm, dp;
255 for (ordinal_type i=0; i<k; i++) {
256 u0 = Teuchos::getCol(Teuchos::View, u, i);
257 nrm = vs.inner_product(u0, u0);
258 dp = vs.inner_product(u2, u0);
259 vs.add2(value_type(1), u2, -dp/nrm, u0, u2);
260 }
261 }
262
263 };
264}
265
266#endif // STOKHOS_LANCZOS_HPP
267
expr val()
Applies Lanczos procedure to a given matrix.
operator_type::value_type value_type
operator_type::ordinal_type ordinal_type
static void computeNormalized(ordinal_type k, const vectorspace_type &vs, const operator_type &A, const vector_type &u_init, matrix_type &u, Teuchos::Array< value_type > &alpha, Teuchos::Array< value_type > &beta, Teuchos::Array< value_type > &nrm_sqrd)
Compute Lanczos basis.
static void compute(ordinal_type k, const vectorspace_type &vs, const operator_type &A, const vector_type &u_init, matrix_type &u, Teuchos::Array< value_type > &alpha, Teuchos::Array< value_type > &beta, Teuchos::Array< value_type > &nrm_sqrd)
Compute Lanczos basis.
Teuchos::SerialDenseVector< ordinal_type, value_type > vector_type
Teuchos::SerialDenseMatrix< ordinal_type, value_type > matrix_type
static void gramSchmidt(ordinal_type k, const vectorspace_type &vs, matrix_type &u, vector_type &u2)
Gram-Schmidt orthogonalization routine.
void add2(const value_type &a, const vector_type &u1, const value_type &b, const vector_type &u2, vector_type &v) const
value_type inner_product(const vector_type &u, const vector_type &v) const
void add3(const value_type &a, const vector_type &u1, const value_type &b, const vector_type &u2, const value_type &c, const vector_type &u3, vector_type &v) const
vector_type create_vector() const
WeightedVectorSpace(const vector_type &weights)
Teuchos::SerialDenseVector< ordinal_type, value_type > vector_type
Top-level namespace for Stokhos classes and functions.