linear_algebra.h
1 /* Copyright (C) 2003-2005 Martin Förg, Rober Huber
2 
3  * This library is free software; you can redistribute it and/or
4  * modify it under the terms of the GNU Lesser General Public
5  * License as published by the Free Software Foundation; either
6  * version 2.1 of the License, or (at your option) any later version.
7  *
8  * This library is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11  * Lesser General Public License for more details.
12  *
13  * You should have received a copy of the GNU Lesser General Public
14  * License along with this library; if not, write to the Free Software
15  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16  *
17  * Contact:
18  * martin.o.foerg@googlemail.com
19  *
20  */
21 
22 #ifndef linear_algebra_h
23 #define linear_algebra_h
24 #include "square_matrix.h"
25 #include <cmath>
26 
27 namespace fmatvec {
28 
34  template <class AT>
36 
37  return RowVector<AT>(x.m,x.lda,x.tp?false:true,x.memory,x.ele).copy();
38  }
39 
45  template <class AT>
47 
48  Vector<AT> y(x.size(),NONINIT);
49 
50  for(int i=0; i<x.size(); i++)
51  y(i)=-x(i);
52 
53  return y;
54  }
55 
62  template <class AT>
63  Vector<AT> operator*(const Vector<AT> &x, const AT& alpha) {
64 
65  Vector<AT> y(x.size(),NONINIT);
66 
67  for(int i=0; i<x.size(); i++)
68  y(i) = x(i)*alpha;
69 
70  return y;
71  }
72 
77  template <class AT>
78  Vector<AT> operator*(const AT& alpha, const Vector<AT> &x) {
79 
80  Vector<AT> y(x.size(),NONINIT);
81 
82  for(int i=0; i<x.size(); i++)
83  y(i) = x(i)*alpha;
84 
85  return y;
86  }
87 
95  template <class AT>
97 
98  return Vector<AT>(x.n,x.lda,x.tp?false:true,x.memory,x.ele).copy();
99  }
100 
106  template <class AT>
108 
109  RowVector<AT> c(a.size(),NONINIT);
110 
111  for(int i=0; i<a.size(); i++)
112  c(i)=-a(i);
113 
114  return c;
115  }
116 
123  template <class AT>
124  RowVector<AT> operator*(const RowVector<AT> &x, const AT& alpha) {
125 
126  RowVector<AT> y(x.size(),NONINIT);
127 
128  for(int i=0; i<x.size(); i++)
129  y(i) = x(i)*alpha;
130 
131  return y;
132  }
133 
138  template <class AT>
139  RowVector<AT> operator*(const AT &alpha, const RowVector<AT> &x) {
140 
141  RowVector<AT> y(x.size(),NONINIT);
142 
143  for(int i=0; i<x.size(); i++)
144  y(i) = x(i)*alpha;
145 
146  return y;
147  }
148 
154  template <class AT>
156 
157  assert(y.size() == x.size());
158 
159  Vector<AT> z(x.size(),NONINIT);
160 
161  for(int i=0; i<x.size(); i++)
162  z(i) = x(i) + y(i);
163 
164  return z;
165  }
166 
172  template <class AT>
174 
175  assert(y.size() == x.size());
176 
177  Vector<AT> z(x.size(),NONINIT);
178 
179  for(int i=0; i<x.size(); i++)
180  z(i) = x(i) - y(i);
181 
182  return z;
183  }
184 
190  template <class AT>
191  AT scalarProduct(const Vector<AT> &x, const Vector<AT > &y) {
192 
193  assert(x.size()==y.size());
194 
195  AT res = 0;
196 
197  for(int i=0; i<x.size(); i++)
198  res += x(i)*y(i);
199 
200  return res;
201  }
202 
208  template <class AT>
210 
211  assert(x.size()==3);
212  assert(y.size()==3);
213 
214  Vector<AT> z(3,NONINIT);
215 
216  z(0) = x(1)*y(2) - x(2)*y(1);
217  z(1) = x(2)*y(0) - x(0)*y(2);
218  z(2) = x(0)*y(1) - x(1)*y(0);
219 
220  return z;
221  }
222 
228  template <class AT>
229  double tripleProduct(const Vector<AT> &a, const Vector<AT> &x, const Vector<AT> &y) {
230 
231  assert(a.size()==3);
232  assert(x.size()==3);
233  assert(y.size()==3);
234 
235  return a(0)*(x(1)*y(2)-x(2)*y(1)) + a(1)*(x(2)*y(0)-x(0)*y(2)) + a(2)*(x(0)*y(1)-x(1)*y(0));
236  }
237 
243  template <class AT>
245 
246  assert(y.size() == x.size());
247 
248  RowVector<AT> z(x.size(),NONINIT);
249 
250  for(int i=0; i<x.size(); i++)
251  z(i) = x(i) - y(i);
252 
253  return z;
254  }
255 
262  template <class AT>
263  AT operator*(const RowVector<AT> &x, const Vector<AT> &y) {
264 
265  assert(x.size() == y.size());
266 
267  AT res=0;
268 
269  for(int i=0; i<x.size(); i++)
270  res+=x(i)*y(i);
271 
272  return res;
273  }
274 
283  template <class AT>
285 
286  return Matrix<General, AT>(A.n,A.m,A.lda,A.tp?false:true,A.memory,A.ele).copy();
287  }
288 
297  template <class AT>
299 
300  return SquareMatrix<AT>(A.n, A.lda, A.tp?false:true, A.memory, A.ele).copy();
301  }
302 
308  template <class AT>
310 
311  SquareMatrix<AT> B(A.size(),NONINIT);
312 
313  for(int i=0; i<A.rows(); i++)
314  for(int j=0; j<A.cols(); j++)
315  B(i,j)=-A(i,j);
316 
317  return B;
318  }
319 
325  template <class AT, class Type>
327 
328  Matrix<Type, AT> C(A.rows(),A.cols(),NONINIT);
329 
330  for(int i=0; i<A.rows(); i++)
331  for(int j=0; j<A.cols(); j++)
332  C(i,j)=-A(i,j);
333 
334  return C;
335  }
336 
345  template <class AT, class Type>
346  Matrix<Type, AT> operator*(const Matrix<Type, AT > &A, const AT &alpha) {
347 
348  Matrix<Type, AT> B(A.rows(),A.cols(),NONINIT);
349 
350  for(int i=0; i<A.rows(); i++)
351  for(int j=0; j<A.cols(); j++)
352  B(i,j) = A(i,j)*alpha;
353 
354  return B;
355  }
356 
361  template <class AT, class Type>
362  Matrix<Type, AT> operator*(const AT &alpha, const Matrix<Type, AT > &A) {
363 
364  Matrix<Type, AT> B(A.rows(),A.cols(),NONINIT);
365 
366  for(int i=0; i<A.rows(); i++)
367  for(int j=0; j<A.cols(); j++)
368  B(i,j) = A(i,j)*alpha;
369 
370  return B;
371  }
372 
384  template <class AT>
386 
387  SquareMatrix< AT> B(x.size(),NONINIT);
388 
389  B(0,0) = 0;
390  B(1,1) = 0;
391  B(2,2) = 0;
392  B(0,1) = -x(2);
393  B(0,2) = x(1);
394  B(1,0) = x(2);
395  B(1,2) = -x(0);
396  B(2,0) = -x(1);
397  B(2,1) = x(0);
398 
399  return B;
400  }
401 
408  template <class AT, class Type>
410 
411  assert(A.cols() == x.size());
412 
413  Vector<AT> z(A.rows(),NONINIT);
414 
415  for(int i=0; i<z.size(); i++) {
416  z(i)=0;
417  for(int j=0; j<x.size(); j++)
418  z(i) += A(i,j) * x(j);
419  }
420 
421  return z;
422  }
423 
430  template <class AT, class Type>
432 
433  assert(x.size() == A.rows());
434 
435  RowVector<AT> z(A.cols(),NONINIT);
436 
437  for(int i=0; i<z.size(); i++) {
438  z(i)=0;
439  for(int j=0; j<x.size(); j++)
440  z(i) += x(j) * A(j,i);
441  }
442 
443  return z;
444  }
445 
451  template <class AT, class Type1, class Type2>
453 
454  assert(A.rows() == B.rows());
455  assert(A.cols() == B.cols());
456 
457  Matrix<General, AT> C(A.rows(),A.cols(),NONINIT);
458  for(int i=0; i<A.rows(); i++)
459  for(int j=0; j<A.cols(); j++)
460  C(i,j) = A(i,j) + B(i,j);
461 
462  return C;
463  }
464 
470  template <class AT, class Type1, class Type2>
472 
473  assert(A.rows() == B.rows());
474  assert(A.cols() == B.cols());
475 
476  Matrix<General, AT> C(A.rows(),A.cols(),NONINIT);
477  for(int i=0; i<A.rows(); i++)
478  for(int j=0; j<A.cols(); j++)
479  C(i,j) = A(i,j) - B(i,j);
480 
481  return C;
482  }
483 
489  template <class AT, class Type1, class Type2>
491 
492  assert(A.cols() == B.rows());
493 
494  Matrix<General, AT> C(A.rows(),B.cols(),NONINIT);
495 
496  for(int i=0; i<C.rows(); i++) {
497  for(int j=0; j<C.cols(); j++) {
498  C(i,j)=0;
499  for(int k=0; k<A.cols(); k++)
500  C(i,j) += A(i,k) * B(k,j);
501  }
502  }
503 
504  return C;
505  }
506 
512  template <class AT, class Type1, class Type2>
514 
515  if(&A == &B)
516  return true;
517 
518  if(A.rows() != B.rows() || A.cols() != B.cols())
519  return false;
520 
521  for(int i=0; i<A.rows(); i++)
522  for(int j=0; j<A.cols(); j++)
523  if(A(i,j)!=B(i,j))
524  return false;
525 
526  return true;
527  }
528 
534  template <class AT, class Type1, class Type2>
536 
537  if(A.rows() != B.rows() || A.cols() != B.cols())
538  return true;
539 
540  for(int i=0; i<A.rows(); i++)
541  for(int j=0; j<A.cols(); j++)
542  if(A(i,j)!=B(i,j))
543  return true;
544 
545  return false;
546  }
547 
554  template <class AT>
556  assert(A.cols() == x.size());
557 
558  Vector<AT> z(A.rows(),NONINIT);
559 
560  const AT *a = A();
561  const int *ia = A.Ip();
562  const int *ja = A.Jp();
563  for(int i=0; i<A.rows(); i++) {
564  z(i) = 0;
565  for(int j=ia[i]; j<ia[i+1]; j++)
566  z(i) += a[j]*x(ja[j]);
567  }
568 
569  return z;
570  }
571 
577  template <class AT>
578  AT max(const Vector<AT> &x) {
579  assert(x.size() > 0);
580  AT maximum = x(0);
581  for(int i=1; i<x.size(); i++) {
582  if(x(i) > maximum)
583  maximum = x(i);
584  }
585  return maximum;
586  }
587 
593  template <class AT>
594  int maxIndex(const Vector<AT> &x) {
595  assert(x.size() > 0);
596  AT maximum = x(0);
597  int index = 0;
598  for(int i=1; i<x.size(); i++) {
599  if(x(i) > maximum) {
600  maximum = x(i);
601  index = i;
602  }
603  }
604  return index;
605  }
606 
612  template <class AT>
613  AT min(const Vector<AT> &x) {
614  assert(x.size() > 0);
615  AT minimum = x(0);
616  for(int i=1; i<x.size(); i++) {
617  if(x(i) < minimum)
618  minimum = x(i);
619  }
620  return minimum;
621  }
622 
628  template <class AT>
629  int minIndex(const Vector<AT> &x) {
630  assert(x.size() > 0);
631  AT minimum = x(0);
632  int index = 0;
633  for(int i=1; i<x.size(); i++) {
634  if(x(i) < minimum) {
635  minimum = x(i);
636  index = i;
637  }
638  }
639  return index;
640  }
641 
642  // HR 28.09.2006
649  template <class AT>
651  assert(A_.rows()>0);
652  assert(A_.cols()>0);
653  assert(A_.cols()> PivotCol);
654  Matrix<General, AT> A = A_.copy();
655  int i,j,N;
656  RowVector<AT > tmp;
657  N = A.rows();
658  for (i=1; i<= N-1; i++) {
659  for (j=0; j< N-1; j++) {
660  if (A(j,PivotCol) > A(j+1,PivotCol)) {
661  tmp = A.row(j);
662  A.row(j) = A.row(j+1);
663  A.row(j+1) = tmp;
664  }
665  }
666  }
667  return A;
668  }
669 
670  // HR 28.09.2006
672  template <class AT>
673  void quicksortmedian_intern(Matrix<General, AT> &A, int PivotCol, RowVector<AT > &tmp, int l, int r){
674 
675  if(r>l){
676  int i=l-1, j=r;
677  //RowVec tmp;
678  if(r-l > 3){ //Median of three
679  int m=l+(r-l)/2;
680  if(A(l,PivotCol)>A(m,PivotCol))
681  { tmp= A.row(l);
682  A.row(l) = A.row(m);
683  A.row(m) =tmp; }
684  if(A(l,PivotCol)> A(r,PivotCol))
685  { tmp= A.row(l);
686  A.row(l) = A.row(r);
687  A.row(r) =tmp; }
688  else if(A(r,PivotCol) > A(m,PivotCol) )
689  { tmp= A.row(r);
690  A.row(r) = A.row(m);
691  A.row(m) =tmp; }
692  }
693 
694  for(;;){
695  while(A(++i,PivotCol) < A(r,PivotCol));
696  while(A(--j,PivotCol) > A(r,PivotCol) && j>i);
697  if(i>=j) break;
698  tmp= A.row(i);
699  A.row(i) = A.row(j);
700  A.row(j) =tmp;
701  }
702  tmp= A.row(i);
703  A.row(i) = A.row(r);
704  A.row(r) =tmp;
705  quicksortmedian_intern(A, PivotCol,tmp, l, i-1);
706  quicksortmedian_intern(A, PivotCol,tmp, i+1, r);
707  }
708  }
709 
710  // HR 28.09.2006
719  template <class AT>
721  Matrix<General, AT> A = A_.copy();
722  int N = A.rows();
723  RowVector<AT> tmp;
724  quicksortmedian_intern(A, PivotCol,tmp, 0, N-1);
725  return A;
726  }
727 
734  template <class AT> int countElements(const SquareMatrix<AT> &A) {
735  int k=0;
736  for(int i=0; i<A.size(); i++) {
737  for(int j=0; j<A.size(); j++) {
738  if(fabs(A(i,j))>1e-16 || i==j) {
739  k++;
740  }
741  }
742  }
743  return k;
744  }
745 }
746 
747 #endif