Newer
Older
// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
// vi: set et ts=4 sw=2 sts=2:
// $Id$
#include <cmath>
#include <cstddef>
#include "exceptions.hh"
#include "fvector.hh"
#include "precision.hh"
@addtogroup DenseMatVec
/*! \file
\brief This file implements a matrix constructed from a given type
representing a field and compile-time given number of rows and columns.
*/
template<class K, int n, int m> class FieldMatrix;
/** @brief Error thrown if operations of a FieldMatrix fail. */
class FMatrixError : public Exception {};
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
// template meta program for assignment from scalar
template<int I>
struct fmmeta_assignscalar {
template<class T, class K>
static void assignscalar (T* x, const K& k)
{
fmmeta_assignscalar<I-1>::assignscalar(x,k);
x[I] = k;
}
};
template<>
struct fmmeta_assignscalar<0> {
template<class T, class K>
static void assignscalar (T* x, const K& k)
{
x[0] = k;
}
};
// template meta program for operator+=
template<int I>
struct fmmeta_plusequal {
template<class T>
static void plusequal (T& x, const T& y)
{
x[I] += y[I];
fmmeta_plusequal<I-1>::plusequal(x,y);
}
};
template<>
struct fmmeta_plusequal<0> {
template<class T>
static void plusequal (T& x, const T& y)
{
x[0] += y[0];
}
};
// template meta program for operator-=
template<int I>
struct fmmeta_minusequal {
template<class T>
static void minusequal (T& x, const T& y)
{
x[I] -= y[I];
fmmeta_minusequal<I-1>::minusequal(x,y);
}
};
template<>
struct fmmeta_minusequal<0> {
template<class T>
static void minusequal (T& x, const T& y)
{
x[0] -= y[0];
}
};
// template meta program for operator*=
template<int I>
struct fmmeta_multequal {
template<class T, class K>
static void multequal (T& x, const K& k)
{
x[I] *= k;
fmmeta_multequal<I-1>::multequal(x,k);
}
};
template<>
struct fmmeta_multequal<0> {
template<class T, class K>
static void multequal (T& x, const K& k)
{
x[0] *= k;
}
};
// template meta program for operator/=
template<int I>
struct fmmeta_divequal {
template<class T, class K>
static void divequal (T& x, const K& k)
{
x[I] /= k;
fmmeta_divequal<I-1>::divequal(x,k);
}
};
template<>
struct fmmeta_divequal<0> {
template<class T, class K>
static void divequal (T& x, const K& k)
{
x[0] /= k;
}
};
// template meta program for dot
template<int I>
struct fmmeta_dot {
template<class X, class Y, class K>
static K dot (const X& x, const Y& y)
{
return x[I]*y[I] + fmmeta_dot<I-1>::template dot<X,Y,K>(x,y);
}
};
template<>
struct fmmeta_dot<0> {
template<class X, class Y, class K>
static K dot (const X& x, const Y& y)
{
return x[0]*y[0];
}
};
// template meta program for umv(x,y)
template<int I>
struct fmmeta_umv {
template<class Mat, class X, class Y, int c>
static void umv (const Mat& A, const X& x, Y& y)
{
typedef typename Mat::row_type R;
typedef typename Mat::field_type K;
y[I] += fmmeta_dot<c>::template dot<R,X,K>(A[I],x);
fmmeta_umv<I-1>::template umv<Mat,X,Y,c>(A,x,y);
}
};
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
template<>
struct fmmeta_umv<0> {
template<class Mat, class X, class Y, int c>
static void umv (const Mat& A, const X& x, Y& y)
{
typedef typename Mat::row_type R;
typedef typename Mat::field_type K;
y[0] += fmmeta_dot<c>::template dot<R,X,K>(A[0],x);
}
};
// template meta program for mmv(x,y)
template<int I>
struct fmmeta_mmv {
template<class Mat, class X, class Y, int c>
static void mmv (const Mat& A, const X& x, Y& y)
{
typedef typename Mat::row_type R;
typedef typename Mat::field_type K;
y[I] -= fmmeta_dot<c>::template dot<R,X,K>(A[I],x);
fmmeta_mmv<I-1>::template mmv<Mat,X,Y,c>(A,x,y);
}
};
template<>
struct fmmeta_mmv<0> {
template<class Mat, class X, class Y, int c>
static void mmv (const Mat& A, const X& x, Y& y)
{
typedef typename Mat::row_type R;
typedef typename Mat::field_type K;
y[0] -= fmmeta_dot<c>::template dot<R,X,K>(A[0],x);
}
};
template<class K, int n, int m, class X, class Y>
inline void fm_mmv (const FieldMatrix<K,n,m>& A, const X& x, Y& y)
{
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
y[i] -= A[i][j]*x[j];
}
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
template<class K>
inline void fm_mmv (const FieldMatrix<K,1,1>& A, const FieldVector<K,1>& x, FieldVector<K,1>& y)
{
y[0] -= A[0][0]*x[0];
}
// template meta program for usmv(x,y)
template<int I>
struct fmmeta_usmv {
template<class Mat, class K, class X, class Y, int c>
static void usmv (const Mat& A, const K& alpha, const X& x, Y& y)
{
typedef typename Mat::row_type R;
y[I] += alpha*fmmeta_dot<c>::template dot<R,X,K>(A[I],x);
fmmeta_usmv<I-1>::template usmv<Mat,K,X,Y,c>(A,alpha,x,y);
}
};
template<>
struct fmmeta_usmv<0> {
template<class Mat, class K, class X, class Y, int c>
static void usmv (const Mat& A, const K& alpha, const X& x, Y& y)
{
typedef typename Mat::row_type R;
y[0] += alpha*fmmeta_dot<c>::template dot<R,X,K>(A[0],x);
}
};
// conjugate komplex does nothing for non-complex types
template<class K>
inline K fm_ck (const K& k)
{
return k;
}
// conjugate komplex
template<class K>
inline std::complex<K> fm_ck (const std::complex<K>& c)
{
return std::complex<K>(c.real(),-c.imag());
}
//! solve small system
template<class K, int n, class V>
void fm_solve (const FieldMatrix<K,n,n>& Ain, V& x, const V& b)
{
// make a copy of a to store factorization
FieldMatrix<K,n,n> A(Ain);
// Gaussian elimination with maximum column pivot
double norm=A.infinity_norm_real(); // for relative thresholds
double pivthres = std::max(FMatrixPrecision<>::absolute_limit(),norm*FMatrixPrecision<>::pivoting_limit());
double singthres = std::max(FMatrixPrecision<>::absolute_limit(),norm*FMatrixPrecision<>::singular_limit());
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
V& rhs = x; // use x to store rhs
rhs = b; // copy data
// elimination phase
for (int i=0; i<n; i++) // loop over all rows
{
double pivmax=fvmeta_absreal(A[i][i]);
// pivoting ?
if (pivmax<pivthres)
{
// compute maximum of row
int imax=i; double abs;
for (int k=i+1; k<n; k++)
if ((abs=fvmeta_absreal(A[k][i]))>pivmax)
{
pivmax = abs; imax = k;
}
// swap rows
if (imax!=i)
for (int j=i; j<n; j++)
std::swap(A[i][j],A[imax][j]);
}
// singular ?
if (pivmax<singthres)
DUNE_THROW(FMatrixError,"matrix is singular");
// eliminate
for (int k=i+1; k<n; k++)
{
K factor = -A[k][i]/A[i][i];
for (int j=i+1; j<n; j++)
A[k][j] += factor*A[i][j];
rhs[k] += factor*rhs[i];
}
}
// backsolve
for (int i=n-1; i>=0; i--)
{
for (int j=i+1; j<n; j++)
rhs[i] -= A[i][j]*x[j];
x[i] = rhs[i]/A[i][i];
}
}
//! special case for 1x1 matrix, x and b may be identical
template<class K, class V>
inline void fm_solve (const FieldMatrix<K,1,1>& A, V& x, const V& b)
{
#ifdef DUNE_FMatrix_WITH_CHECKING
if (fvmeta_absreal(A[0][0])<FMatrixPrecision<>::absolute_limit())
DUNE_THROW(FMatrixError,"matrix is singular");
#endif
x[0] = b[0]/A[0][0];
}
//! special case for 2x2 matrix, x and b may be identical
template<class K, class V>
inline void fm_solve (const FieldMatrix<K,2,2>& A, V& x, const V& b)
{
#ifdef DUNE_FMatrix_WITH_CHECKING
if (fvmeta_absreal(detinv)<FMatrixPrecision<>::absolute_limit())
DUNE_THROW(FMatrixError,"matrix is singular");
detinv = 1/detinv;
#else
K detinv = 1.0/(A[0][0]*A[1][1]-A[0][1]*A[1][0]);
#endif
K temp = b[0];
x[0] = detinv*(A[1][1]*b[0]-A[0][1]*b[1]);
x[1] = detinv*(A[0][0]*b[1]-A[1][0]*temp);
}
//! compute inverse
template<class K, int n>
void fm_invert (FieldMatrix<K,n,n>& B)
{
FieldMatrix<K,n,n> A(B);
FieldMatrix<K,n,n>& L=A;
FieldMatrix<K,n,n>& U=A;
double norm=A.infinity_norm_real(); // for relative thresholds
double pivthres = std::max(FMatrixPrecision<>::absolute_limit(),norm*FMatrixPrecision<>::pivoting_limit());
double singthres = std::max(FMatrixPrecision<>::absolute_limit(),norm*FMatrixPrecision<>::singular_limit());
// LU decomposition of A in A
for (int i=0; i<n; i++) // loop over all rows
{
double pivmax=fvmeta_absreal(A[i][i]);
// pivoting ?
if (pivmax<pivthres)
{
// compute maximum of column
int imax=i; double abs;
for (int k=i+1; k<n; k++)
if ((abs=fvmeta_absreal(A[k][i]))>pivmax)
{
pivmax = abs; imax = k;
}
// swap rows
if (imax!=i)
for (int j=i; j<n; j++)
std::swap(A[i][j],A[imax][j]);
}
// singular ?
if (pivmax<singthres)
DUNE_THROW(FMatrixError,"matrix is singular");
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
// eliminate
for (int k=i+1; k<n; k++)
{
K factor = A[k][i]/A[i][i];
L[k][i] = factor;
for (int j=i+1; j<n; j++)
A[k][j] -= factor*A[i][j];
}
}
// initialize inverse
B = 0;
for (int i=0; i<n; i++) B[i][i] = 1;
// L Y = I; multiple right hand sides
for (int i=0; i<n; i++)
for (int j=0; j<i; j++)
for (int k=0; k<n; k++)
B[i][k] -= L[i][j]*B[j][k];
// U A^{-1} = Y
for (int i=n-1; i>=0; i--)
for (int k=0; k<n; k++)
{
for (int j=i+1; j<n; j++)
B[i][k] -= U[i][j]*B[j][k];
B[i][k] /= U[i][i];
}
}
//! compute inverse n=1
template<class K>
void fm_invert (FieldMatrix<K,1,1>& A)
{
#ifdef DUNE_FMatrix_WITH_CHECKING
if (fvmeta_absreal(A[0][0])<FMatrixPrecision<>::absolute_limit())
DUNE_THROW(FMatrixError,"matrix is singular");
#endif
A[0][0] = 1/A[0][0];
}
//! compute inverse n=2
template<class K>
void fm_invert (FieldMatrix<K,2,2>& A)
{
K detinv = A[0][0]*A[1][1]-A[0][1]*A[1][0];
#ifdef DUNE_FMatrix_WITH_CHECKING
if (fvmeta_absreal(detinv)<FMatrixPrecision<>::absolute_limit())
DUNE_THROW(FMatrixError,"matrix is singular");
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
#endif
detinv = 1/detinv;
K temp=A[0][0];
A[0][0] = A[1][1]*detinv;
A[0][1] = -A[0][1]*detinv;
A[1][0] = -A[1][0]*detinv;
A[1][1] = temp*detinv;
}
//! left multiplication with matrix
template<class K, int n, int m>
void fm_leftmultiply (const FieldMatrix<K,n,n>& M, FieldMatrix<K,n,m>& A)
{
FieldMatrix<K,n,m> C(A);
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
{
A[i][j] = 0;
for (int k=0; k<n; k++)
A[i][j] += M[i][k]*C[k][j];
}
}
//! left multiplication with matrix, n=1
template<class K>
void fm_leftmultiply (const FieldMatrix<K,1,1>& M, FieldMatrix<K,1,1>& A)
{
A[0][0] *= M[0][0];
}
//! left multiplication with matrix, n=2
template<class K>
void fm_leftmultiply (const FieldMatrix<K,2,2>& M, FieldMatrix<K,2,2>& A)
{
FieldMatrix<K,2,2> C(A);
A[0][0] = M[0][0]*C[0][0] + M[0][1]*C[1][0];
A[0][1] = M[0][0]*C[0][1] + M[0][1]*C[1][1];
A[1][0] = M[1][0]*C[0][0] + M[1][1]*C[1][0];
A[1][1] = M[1][0]*C[0][1] + M[1][1]*C[1][1];
}
//! right multiplication with matrix
template<class K, int n, int m>
void fm_rightmultiply (const FieldMatrix<K,m,m>& M, FieldMatrix<K,n,m>& A)
{
FieldMatrix<K,n,m> C(A);
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
{
A[i][j] = 0;
for (int k=0; k<m; k++)
A[i][j] += C[i][k]*M[k][j];
}
}
//! right multiplication with matrix, n=1
template<class K>
void fm_rightmultiply (const FieldMatrix<K,1,1>& M, FieldMatrix<K,1,1>& A)
{
A[0][0] *= M[0][0];
}
//! right multiplication with matrix, n=2
template<class K>
void fm_rightmultiply (const FieldMatrix<K,2,2>& M, FieldMatrix<K,2,2>& A)
{
FieldMatrix<K,2,2> C(A);
A[0][0] = C[0][0]*M[0][0] + C[0][1]*M[1][0];
A[0][1] = C[0][0]*M[0][1] + C[0][1]*M[1][1];
A[1][0] = C[1][0]*M[0][0] + C[1][1]*M[1][0];
A[1][1] = C[1][0]*M[0][1] + C[1][1]*M[1][1];
}
/**
@brief A dense n x m matrix.
Matrices represent linear maps from a vector space V to a vector space W.
This class represents such a linear map by storing a two-dimensional
array of numbers of a given field type K. The number of rows and
columns is given at compile time.
Implementation of all members uses template meta programs where appropriate
*/
#ifdef DUNE_EXPRESSIONTEMPLATES
template<class K, int n, int m>
class FieldMatrix : ExprTmpl::Matrix< FieldMatrix<K,n,m> >
#else
template<class K, int n, int m>
class FieldMatrix
{
public:
// standard constructor and everything is sufficient ...
//===== type definitions and constants
//! export the type representing the field
typedef K field_type;
//! export the type representing the components
typedef K block_type;
//! The type used for the index access and size operations.
typedef std::size_t size_type;
enum {
//! The number of block levels we contain. This is 1.
blocklevel = 1
};
//! Each row is implemented by a field vector
typedef FieldVector<K,m> row_type;
//! export size
enum {
//! The number of rows.
rows = n,
//! The number of columns.
cols = m
};
//===== constructors
/** \brief Default constructor
*/
FieldMatrix () {}
/** \brief Constructor initializing the whole matrix with a scalar
*/
FieldMatrix (const K& k)
{
for (size_type i=0; i<n; i++) p[i] = k;
}
//===== random access interface to rows of the matrix
//! random access to the rows
row_type& operator[] (size_type i)
#ifdef DUNE_FMatrix_WITH_CHECKING
if (i<0 || i>=n) DUNE_THROW(FMatrixError,"index out of range");
#endif
return p[i];
}
//! same for read only access
const row_type& operator[] (size_type i) const
#ifdef DUNE_FMatrix_WITH_CHECKING
if (i<0 || i>=n) DUNE_THROW(FMatrixError,"index out of range");
#endif
return p[i];
}
//===== iterator interface to rows of the matrix
//! Iterator class for sequential access
typedef FieldIterator<FieldMatrix<K,n,m>,row_type> Iterator;
//! typedef for stl compliant access
typedef Iterator iterator;
//! rename the iterators for easier access
typedef Iterator RowIterator;
//! rename the iterators for easier access
typedef typename row_type::Iterator ColIterator;
return Iterator(*this,0);
}
//! end iterator
Iterator end ()
{
return Iterator(*this,n);
}
//! begin iterator
Iterator rbegin ()
{
return Iterator(*this,n-1);
}
//! end iterator
Iterator rend ()
{
return Iterator(*this,-1);
//! Iterator class for sequential access
typedef FieldIterator<const FieldMatrix<K,n,m>,const row_type> ConstIterator;
//! typedef for stl compliant access
typedef ConstIterator const_iterator;
typedef ConstIterator ConstRowIterator;
//! rename the iterators for easier access
typedef typename row_type::ConstIterator ConstColIterator;
//! begin iterator
ConstIterator begin () const
{
return ConstIterator(*this,0);
}
//! end iterator
ConstIterator end () const
{
return ConstIterator(*this,n);
}
//! begin iterator
ConstIterator rbegin () const
{
return ConstIterator(*this,n-1);
}
//! end iterator
ConstIterator rend () const
{
return ConstIterator(*this,-1);
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
}
//===== assignment from scalar
FieldMatrix& operator= (const K& k)
{
fmmeta_assignscalar<n-1>::assignscalar(p,k);
return *this;
}
//===== vector space arithmetic
//! vector space addition
FieldMatrix& operator+= (const FieldMatrix& y)
{
fmmeta_plusequal<n-1>::plusequal(*this,y);
return *this;
}
//! vector space subtraction
FieldMatrix& operator-= (const FieldMatrix& y)
{
fmmeta_minusequal<n-1>::minusequal(*this,y);
return *this;
}
//! vector space multiplication with scalar
FieldMatrix& operator*= (const K& k)
{
fmmeta_multequal<n-1>::multequal(*this,k);
return *this;
}
//! vector space division by scalar
FieldMatrix& operator/= (const K& k)
{
fmmeta_divequal<n-1>::divequal(*this,k);
return *this;
}
//===== linear maps
//! y += A x
template<class X, class Y>
void umv (const X& x, Y& y) const
{
#ifdef DUNE_FMatrix_WITH_CHECKING
if (x.N()!=M()) DUNE_THROW(FMatrixError,"index out of range");
if (y.N()!=N()) DUNE_THROW(FMatrixError,"index out of range");
#endif
fmmeta_umv<n-1>::template umv<FieldMatrix,X,Y,m-1>(*this,x,y);
// for (int i=0; i<n; i++)
// for (int j=0; j<m; j++)
// y[i] += (*this)[i][j] * x[j];
}
//! y += A^T x
template<class X, class Y>
void umtv (const X& x, Y& y) const
{
#ifdef DUNE_FMatrix_WITH_CHECKING
if (x.N()!=N()) DUNE_THROW(FMatrixError,"index out of range");
if (y.N()!=M()) DUNE_THROW(FMatrixError,"index out of range");
for (size_type i=0; i<n; i++)
for (size_type j=0; j<m; j++)
y[j] += p[i][j]*x[i];
}
//! y += A^H x
template<class X, class Y>
void umhv (const X& x, Y& y) const
{
#ifdef DUNE_FMatrix_WITH_CHECKING
if (x.N()!=N()) DUNE_THROW(FMatrixError,"index out of range");
if (y.N()!=M()) DUNE_THROW(FMatrixError,"index out of range");
for (size_type i=0; i<n; i++)
for (size_type j=0; j<m; j++)
y[j] += fm_ck(p[i][j])*x[i];
}
//! y -= A x
template<class X, class Y>
void mmv (const X& x, Y& y) const
{
#ifdef DUNE_FMatrix_WITH_CHECKING
if (x.N()!=M()) DUNE_THROW(FMatrixError,"index out of range");
if (y.N()!=N()) DUNE_THROW(FMatrixError,"index out of range");
#endif
fmmeta_mmv<n-1>::template mmv<FieldMatrix,X,Y,m-1>(*this,x,y);
//fm_mmv(*this,x,y);
}
//! y -= A^T x
template<class X, class Y>
void mmtv (const X& x, Y& y) const
{
#ifdef DUNE_FMatrix_WITH_CHECKING
if (x.N()!=N()) DUNE_THROW(FMatrixError,"index out of range");
if (y.N()!=M()) DUNE_THROW(FMatrixError,"index out of range");
for (size_type i=0; i<n; i++)
for (size_type j=0; j<m; j++)
y[j] -= p[i][j]*x[i];
}
//! y -= A^H x
template<class X, class Y>
void mmhv (const X& x, Y& y) const
{
#ifdef DUNE_FMatrix_WITH_CHECKING
if (x.N()!=N()) DUNE_THROW(FMatrixError,"index out of range");
if (y.N()!=M()) DUNE_THROW(FMatrixError,"index out of range");
for (size_type i=0; i<n; i++)
for (size_type j=0; j<m; j++)
y[j] -= fm_ck(p[i][j])*x[i];
}
//! y += alpha A x
template<class X, class Y>
void usmv (const K& alpha, const X& x, Y& y) const
{
#ifdef DUNE_FMatrix_WITH_CHECKING
if (x.N()!=M()) DUNE_THROW(FMatrixError,"index out of range");
if (y.N()!=N()) DUNE_THROW(FMatrixError,"index out of range");
#endif
fmmeta_usmv<n-1>::template usmv<FieldMatrix,K,X,Y,m-1>(*this,alpha,x,y);
}
//! y += alpha A^T x
template<class X, class Y>
void usmtv (const K& alpha, const X& x, Y& y) const
{
#ifdef DUNE_FMatrix_WITH_CHECKING
if (x.N()!=N()) DUNE_THROW(FMatrixError,"index out of range");
if (y.N()!=M()) DUNE_THROW(FMatrixError,"index out of range");
for (size_type i=0; i<n; i++)
for (size_type j=0; j<m; j++)
y[j] += alpha*p[i][j]*x[i];
}
//! y += alpha A^H x
template<class X, class Y>
void usmhv (const K& alpha, const X& x, Y& y) const
{
#ifdef DUNE_FMatrix_WITH_CHECKING
if (x.N()!=N()) DUNE_THROW(FMatrixError,"index out of range");
if (y.N()!=M()) DUNE_THROW(FMatrixError,"index out of range");
for (size_type i=0; i<n; i++)
for (size_type j=0; j<m; j++)
y[j] += alpha*fm_ck(p[i][j])*x[i];
}
//===== norms
//! frobenius norm: sqrt(sum over squared values of entries)
double frobenius_norm () const
{
double sum=0;
for (size_type i=0; i<n; ++i) sum += p[i].two_norm2();
return sqrt(sum);
}
//! square of frobenius norm, need for block recursion
double frobenius_norm2 () const
{
double sum=0;
for (size_type i=0; i<n; ++i) sum += p[i].two_norm2();
return sum;
}
//! infinity norm (row sum norm, how to generalize for blocks?)
double infinity_norm () const
{
double max=0;
for (size_type i=0; i<n; ++i) max = std::max(max,p[i].one_norm());
return max;
}
//! simplified infinity norm (uses Manhattan norm for complex values)
double infinity_norm_real () const
{
double max=0;
for (size_type i=0; i<n; ++i) max = std::max(max,p[i].one_norm_real());
return max;
}
//===== solve
/** \brief Solve system A x = b
*
* \exception FMatrixError if the matrix is singular
*/
template<class V>
void solve (V& x, const V& b) const
{
fm_solve(*this,x,b);
}
/** \brief Compute inverse
*
* \exception FMatrixError if the matrix is singular
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
*/
void invert ()
{
fm_invert(*this);
}
//! calculates the determinant of this matrix
K determinant () const;
//! Multiplies M from the left to this matrix
FieldMatrix& leftmultiply (const FieldMatrix<K,n,n>& M)
{
fm_leftmultiply(M,*this);
return *this;
}
//! Multiplies M from the right to this matrix
FieldMatrix& rightmultiply (const FieldMatrix<K,n,n>& M)
{
fm_rightmultiply(M,*this);
return *this;
}
//===== sizes
//! number of blocks in row direction
size_type N () const
{
return n;
}
//! number of blocks in column direction
size_type M () const
{
return m;
}
//! row dimension of block r
size_type rowdim (size_type r) const
{
return 1;
}
//! col dimension of block c
size_type coldim (size_type c) const
{
return 1;
}
//! dimension of the destination vector space
size_type rowdim () const
{
return n;
}
//! dimension of the source vector space
size_type coldim () const
{
return m;
}
//===== query
//! return true when (i,j) is in pattern
bool exists (size_type i, size_type j) const
#ifdef DUNE_FMatrix_WITH_CHECKING
if (i<0 || i>=n) DUNE_THROW(FMatrixError,"index out of range");
if (j<0 || i>=m) DUNE_THROW(FMatrixError,"index out of range");
#endif
return true;
}
//===== conversion operator
/** \brief Sends the matrix to an output stream */
void print (std::ostream& s) const
{
for (size_type i=0; i<n; i++)
s << p[i] << std::endl;
}
/** \brief Sends the matrix to an output stream */
friend std::ostream& operator<< (std::ostream& s, const FieldMatrix<K,n,m>& a)
{
a.print(s);
return s;
}
private:
// the data, very simply a built in array with rowwise ordering
row_type p[n];
};
namespace HelpMat {
// calculation of determinat of matrix
template <class K, int row,int col>
static inline K determinantMatrix (const FieldMatrix<K,row,col> &matrix)
{
if (row!=col)
DUNE_THROW(FMatrixError, "There is no determinant for a " << row << "x" << col << " matrix!");
DUNE_THROW(FMatrixError, "No implementation of determinantMatrix "
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
<< "for FieldMatrix<" << row << "," << col << "> !");
return 0.0;
}
template <typename K>
static inline K determinantMatrix (const FieldMatrix<K,1,1> &matrix)
{
return matrix[0][0];
}
template <typename K>
static inline K determinantMatrix (const FieldMatrix<K,2,2> &matrix)
{
return matrix[0][0]*matrix[1][1] - matrix[0][1]*matrix[1][0];
}
template <typename K>
static inline K determinantMatrix (const FieldMatrix<K,3,3> &matrix)
{
// code generated by maple
K t4 = matrix[0][0] * matrix[1][1];
K t6 = matrix[0][0] * matrix[1][2];
K t8 = matrix[0][1] * matrix[1][0];
K t10 = matrix[0][2] * matrix[1][0];
K t12 = matrix[0][1] * matrix[2][0];
K t14 = matrix[0][2] * matrix[2][0];
K det = (t4*matrix[2][2]-t6*matrix[2][1]-t8*matrix[2][2]+
t10*matrix[2][1]+t12*matrix[1][2]-t14*matrix[1][1]);
return det;
}
} // end namespace HelpMat
// implementation of the determinant
template <class K, int n, int m>
inline K FieldMatrix<K,n,m>::determinant () const
{
return HelpMat::determinantMatrix(*this);
}
/** \brief Special type for 1x1 matrices
*/
template<class K>
class FieldMatrix<K,1,1>
{
public:
// standard constructor and everything is sufficient ...
//===== type definitions and constants
//! export the type representing the field
typedef K field_type;
//! export the type representing the components
typedef K block_type;
//! The type used for index access and size operations
typedef int size_type;
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
//! We are at the leaf of the block recursion
enum {
//! The number of block levels we contain.
//! This is always one for this type.
blocklevel = 1
};
//! Each row is implemented by a field vector
typedef FieldVector<K,1> row_type;
//! export size
enum {
//! \brief The number of rows.
//! This is always one for this type.
rows = 1,
n = 1,
//! \brief The number of columns.
//! This is always one for this type.
cols = 1,
m = 1
};
Oliver Sander
committed
//===== constructors
/** \brief Default constructor
*/
FieldMatrix () {}
/** \brief Constructor initializing the whole matrix with a scalar
*/
FieldMatrix (const K& k)
{
a = k;
}
//===== random access interface to rows of the matrix
//! random access to the rows
row_type& operator[] (size_type i)
{
#ifdef DUNE_FMatrix_WITH_CHECKING
if (i<0 || i>=n) DUNE_THROW(FMatrixError,"index out of range");
#endif
return a;
}
//! same for read only access
const row_type& operator[] (size_type i) const
{
#ifdef DUNE_FMatrix_WITH_CHECKING
if (i<0 || i>=n) DUNE_THROW(FMatrixError,"index out of range");
#endif
return a;
}
//===== iterator interface to rows of the matrix
//! Iterator class for sequential access
typedef FieldIterator<FieldMatrix<K,n,m>,row_type> Iterator;
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
//! typedef for stl compliant access
typedef Iterator iterator;
//! rename the iterators for easier access
typedef Iterator RowIterator;
//! rename the iterators for easier access
typedef typename row_type::Iterator ColIterator;
//! begin iterator
Iterator begin ()
{
return Iterator(*this,0);
}
//! end iterator
Iterator end ()
{
return Iterator(*this,n);
}
//! begin iterator
Iterator rbegin ()
{
return Iterator(*this,n-1);
}
//! end iterator
Iterator rend ()
{
return Iterator(*this,-1);
}
//! Iterator class for sequential access
typedef FieldIterator<const FieldMatrix<K,n,m>,const row_type> ConstIterator;
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
//! typedef for stl compliant access
typedef ConstIterator const_iterator;
//! rename the iterators for easier access
typedef ConstIterator ConstRowIterator;
//! rename the iterators for easier access
typedef typename row_type::ConstIterator ConstColIterator;
//! begin iterator
ConstIterator begin () const
{
return ConstIterator(*this,0);
}
//! end iterator
ConstIterator end () const
{
return ConstIterator(*this,n);
}
//! begin iterator
ConstIterator rbegin () const
{
return ConstIterator(*this,n-1);
}
//! end iterator
ConstIterator rend () const
{
return ConstIterator(*this,-1);
}
//===== assignment from scalar
FieldMatrix& operator= (const K& k)
{
a[0] = k;
return *this;
}
//===== vector space arithmetic
//! vector space addition
FieldMatrix& operator+= (const K& y)
{
a[0] += y;
return *this;
}
//! vector space subtraction
FieldMatrix& operator-= (const K& y)
{
a[0] -= y;
return *this;
}
//! vector space multiplication with scalar
FieldMatrix& operator*= (const K& k)
{
a[0] *= k;
return *this;
}
//! vector space division by scalar
FieldMatrix& operator/= (const K& k)
{
a[0] /= k;
return *this;
}
//===== linear maps
//! y += A x
void umv (const FieldVector<K,1>& x, FieldVector<K,1>& y) const
{
y.p += a[0] * x.p;
}
//! y += A^T x
void umtv (const FieldVector<K,1>& x, FieldVector<K,1>& y) const
{
y.p += a[0] * x.p;
}
//! y += A^H x
void umhv (const FieldVector<K,1>& x, FieldVector<K,1>& y) const
{
y.p += fm_ck(a[0]) * x.p;
}
//! y -= A x
void mmv (const FieldVector<K,1>& x, FieldVector<K,1>& y) const
{
y.p -= a[0] * x.p;
}
//! y -= A^T x
void mmtv (const FieldVector<K,1>& x, FieldVector<K,1>& y) const
{
y.p -= a[0] * x.p;
}
//! y -= A^H x
void mmhv (const FieldVector<K,1>& x, FieldVector<K,1>& y) const
{
y.p -= fm_ck(a[0]) * x.p;
}
//! y += alpha A x
void usmv (const K& alpha, const FieldVector<K,1>& x, FieldVector<K,1>& y) const
{
y.p += alpha * a[0] * x.p;
}
//! y += alpha A^T x
void usmtv (const K& alpha, const FieldVector<K,1>& x, FieldVector<K,1>& y) const
{
y.p += alpha * a[0] * x.p;
}
//! y += alpha A^H x
void usmhv (const K& alpha, const FieldVector<K,1>& x, FieldVector<K,1>& y) const
{
y.p += alpha * fm_ck(a[0]) * x.p;
}
//===== norms
//! frobenius norm: sqrt(sum over squared values of entries)
double frobenius_norm () const
{
return sqrt(fvmeta_abs2(a[0]));
}
//! square of frobenius norm, need for block recursion
double frobenius_norm2 () const
{
return fvmeta_abs2(a[0]);
}
//! infinity norm (row sum norm, how to generalize for blocks?)
double infinity_norm () const
{
return fvmeta_abs(a[0]);
}
//! simplified infinity norm (uses Manhattan norm for complex values)
double infinity_norm_real () const
{
return fvmeta_abs_real(a[0]);
}
//===== solve
//! Solve system A x = b
void solve (FieldVector<K,1>& x, const FieldVector<K,1>& b) const
{
x.p = b.p/a[0];
}
//! compute inverse
void invert ()
{
a[0] = 1/a[0];
}
//! left multiplication
FieldMatrix& leftmultiply (const FieldMatrix& M)
{
a[0] *= M.a[0];
return *this;
}
//! left multiplication
FieldMatrix& rightmultiply (const FieldMatrix& M)
{
a[0] *= M.a[0];
return *this;
}
//===== sizes
//! number of blocks in row direction
size_type N () const
{
return 1;
}
//! number of blocks in column direction
size_type M () const
{
return 1;
}
//! row dimension of block r
size_type rowdim (size_type r) const
{
return 1;
}
//! col dimension of block c
size_type coldim (size_type c) const
{
return 1;
}
//! dimension of the destination vector space
size_type rowdim () const
{
return 1;
}
//! dimension of the source vector space
size_type coldim () const
{
return 1;
}
//===== query
//! return true when (i,j) is in pattern
bool exists (size_type i, size_type j) const
{
return i==0 && j==0;
}
//===== conversion operator
operator K () const {return a[0];}
private:
// the data, just a single row with a single scalar
row_type a;
};
Robert Klöfkorn
committed
namespace FMatrixHelp {
//! invert scalar without changing the original matrix
template <typename K>
static inline K invertMatrix (const FieldMatrix<K,1,1> &matrix, FieldMatrix<K,1,1> &inverse)
{
Robert Klöfkorn
committed
}
//! invert scalar without changing the original matrix
template <typename K>
static inline K invertMatrix_retTransposed (const FieldMatrix<K,1,1> &matrix, FieldMatrix<K,1,1> &inverse)
{
return invertMatrix(matrix,inverse);
}
Robert Klöfkorn
committed
//! invert 2x2 Matrix without changing the original matrix
template <typename K>
static inline K invertMatrix (const FieldMatrix<K,2,2> &matrix, FieldMatrix<K,2,2> &inverse)
{
// code generated by maple
K det = (matrix[0][0]*matrix[1][1] - matrix[0][1]*matrix[1][0]);
K det_1 = 1.0/det;
inverse[0][0] = matrix[1][1] * det_1;
inverse[0][1] = - matrix[0][1] * det_1;
inverse[1][0] = - matrix[1][0] * det_1;
inverse[1][1] = matrix[0][0] * det_1;
return det;
}
//! invert 2x2 Matrix without changing the original matrix
//! return transposed matrix
template <typename K>
static inline K invertMatrix_retTransposed (const FieldMatrix<K,2,2> &matrix, FieldMatrix<K,2,2> &inverse)
{
// code generated by maple
K det = (matrix[0][0]*matrix[1][1] - matrix[0][1]*matrix[1][0]);
K det_1 = 1.0/det;
inverse[0][0] = matrix[1][1] * det_1;
inverse[1][0] = - matrix[0][1] * det_1;
inverse[0][1] = - matrix[1][0] * det_1;
inverse[1][1] = matrix[0][0] * det_1;
return det;
}
Robert Klöfkorn
committed
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
//! invert 3x3 Matrix without changing the original matrix
template <typename K>
static inline K invertMatrix (const FieldMatrix<K,3,3> &matrix, FieldMatrix<K,3,3> &inverse)
{
// code generated by maple
K t4 = matrix[0][0] * matrix[1][1];
K t6 = matrix[0][0] * matrix[1][2];
K t8 = matrix[0][1] * matrix[1][0];
K t10 = matrix[0][2] * matrix[1][0];
K t12 = matrix[0][1] * matrix[2][0];
K t14 = matrix[0][2] * matrix[2][0];
K det = (t4*matrix[2][2]-t6*matrix[2][1]-t8*matrix[2][2]+
t10*matrix[2][1]+t12*matrix[1][2]-t14*matrix[1][1]);
K t17 = 1.0/det;
inverse[0][0] = (matrix[1][1] * matrix[2][2] - matrix[1][2] * matrix[2][1])*t17;
inverse[0][1] = -(matrix[0][1] * matrix[2][2] - matrix[0][2] * matrix[2][1])*t17;
inverse[0][2] = (matrix[0][1] * matrix[1][2] - matrix[0][2] * matrix[1][1])*t17;
inverse[1][0] = -(matrix[1][0] * matrix[2][2] - matrix[1][2] * matrix[2][0])*t17;
inverse[1][1] = (matrix[0][0] * matrix[2][2] - t14) * t17;
inverse[1][2] = -(t6-t10) * t17;
inverse[2][0] = (matrix[1][0] * matrix[2][1] - matrix[1][1] * matrix[2][0]) * t17;
inverse[2][1] = -(matrix[0][0] * matrix[2][1] - t12) * t17;
inverse[2][2] = (t4-t8) * t17;
return det;
}
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
//! invert 3x3 Matrix without changing the original matrix
template <typename K>
static inline K invertMatrix_retTransposed (const FieldMatrix<K,3,3> &matrix, FieldMatrix<K,3,3> &inverse)
{
// code generated by maple
K t4 = matrix[0][0] * matrix[1][1];
K t6 = matrix[0][0] * matrix[1][2];
K t8 = matrix[0][1] * matrix[1][0];
K t10 = matrix[0][2] * matrix[1][0];
K t12 = matrix[0][1] * matrix[2][0];
K t14 = matrix[0][2] * matrix[2][0];
K det = (t4*matrix[2][2]-t6*matrix[2][1]-t8*matrix[2][2]+
t10*matrix[2][1]+t12*matrix[1][2]-t14*matrix[1][1]);
K t17 = 1.0/det;
inverse[0][0] = (matrix[1][1] * matrix[2][2] - matrix[1][2] * matrix[2][1])*t17;
inverse[1][0] = -(matrix[0][1] * matrix[2][2] - matrix[0][2] * matrix[2][1])*t17;
inverse[2][0] = (matrix[0][1] * matrix[1][2] - matrix[0][2] * matrix[1][1])*t17;
inverse[0][1] = -(matrix[1][0] * matrix[2][2] - matrix[1][2] * matrix[2][0])*t17;
inverse[1][1] = (matrix[0][0] * matrix[2][2] - t14) * t17;
inverse[2][1] = -(t6-t10) * t17;
inverse[0][2] = (matrix[1][0] * matrix[2][1] - matrix[1][1] * matrix[2][0]) * t17;
inverse[1][2] = -(matrix[0][0] * matrix[2][1] - t12) * t17;
inverse[2][2] = (t4-t8) * t17;
return det;
}
//! calculates ret = matrix * x
template <typename K, int dim>
static void multAssign(const FieldMatrix<K,dim,dim> &matrix, const FieldVector<K,dim> & x, FieldVector<K,dim> & ret)
{
typedef typename FieldMatrix<K,dim,dim>::size_type size_type;
for(size_type i=0; i<dim; i++)
for(size_type j=0; j<dim; j++)
{
ret[i] += matrix[i][j]*x[j];
}
}
}
//! calculates ret = matrix * x
template <typename K, int dim>
static FieldVector<K,dim> mult(const FieldMatrix<K,dim,dim> &matrix, const FieldVector<K,dim> & x)
{
FieldVector<K,dim> ret;
multAssign(matrix,x,ret);
return ret;
}
//! calculates ret = matrix^T * x
template <typename K, int dim>
static FieldVector<K,dim> multTransposed(const FieldMatrix<K,dim,dim> &matrix, const FieldVector<K,dim> & x)
{
FieldVector<K,dim> ret;
typedef typename FieldMatrix<K,dim,dim>::size_type size_type;
for(size_type i=0; i<dim; i++)
{
ret[i] = 0.0;
for(size_type j=0; j<dim; j++)
{
ret[i] += matrix[j][i]*x[j];
}
}
return ret;
}
Robert Klöfkorn
committed
} // end namespace FMatrixHelp
#ifdef DUNE_EXPRESSIONTEMPLATES
template <class K, int N, int M>
struct BlockType< FieldMatrix<K,N,M> >
{
typedef K type;
};
template <class K, int N, int M>
struct FieldType< FieldMatrix<K,N,M> >
{
typedef K type;
};
#endif // DUNE_EXPRESSIONTEMPLATES
Robert Klöfkorn
committed
/** @} end documentation */
} // end namespace
#endif