src/math/SquareMatrix.hpp

/*
 * Copyright (c) 2005 The University of Notre Dame. All Rights Reserved.
 *
 * The University of Notre Dame grants you ("Licensee") a
 * non-exclusive, royalty free, license to use, modify and
 * redistribute this software in source and binary code form, provided
 * that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the
 *    distribution.
 *
 * This software is provided "AS IS," without a warranty of any
 * kind. All express or implied conditions, representations and
 * warranties, including any implied warranty of merchantability,
 * fitness for a particular purpose or non-infringement, are hereby
 * excluded.  The University of Notre Dame and its licensors shall not
 * be liable for any damages suffered by licensee as a result of
 * using, modifying or distributing the software or its
 * derivatives. In no event will the University of Notre Dame or its
 * licensors be liable for any lost revenue, profit or data, or for
 * direct, indirect, special, consequential, incidental or punitive
 * damages, however caused and regardless of the theory of liability,
 * arising out of the use of or inability to use software, even if the
 * University of Notre Dame has been advised of the possibility of
 * such damages.
 *
 * SUPPORT OPEN SCIENCE!  If you use OpenMD or its source code in your
 * research, please cite the appropriate papers when you publish your
 * work.  Good starting points are:
 *                                                                      
 * [1]  Meineke, et al., J. Comp. Chem. 26, 252-271 (2005).             
 * [2]  Fennell & Gezelter, J. Chem. Phys. 124, 234104 (2006).          
 * [3]  Sun, Lin & Gezelter, J. Chem. Phys. 128, 234107 (2008).          
 * [4]  Kuang & Gezelter,  J. Chem. Phys. 133, 164101 (2010).
 * [5]  Vardeman, Stocker & Gezelter, J. Chem. Theory Comput. 7, 834 (2011).
 */
 
/**
 * @file SquareMatrix.hpp
 * @author Teng Lin
 * @date 10/11/2004
 * @version 1.0
 */
#ifndef MATH_SQUAREMATRIX_HPP 
#define MATH_SQUAREMATRIX_HPP 

#include "math/RectMatrix.hpp"
#include "utils/NumericConstant.hpp"

namespace OpenMD {

  /**
   * @class SquareMatrix SquareMatrix.hpp "math/SquareMatrix.hpp"
   * @brief A square matrix class
   * \tparam Real the element type
   * \tparam Dim the dimension of the square matrix
   */
  template<typename Real, int Dim>
  class SquareMatrix : public RectMatrix<Real, Dim, Dim> {
  public:
    typedef Real ElemType;
    typedef Real* ElemPoinerType;

    /** default constructor */
    SquareMatrix() {
      for (unsigned int i = 0; i < Dim; i++)
        for (unsigned int j = 0; j < Dim; j++)
          this->data_[i][j] = 0.0;
    }

    /** Constructs and initializes every element of this matrix to a scalar */ 
    SquareMatrix(Real s) : RectMatrix<Real, Dim, Dim>(s){
    }

    /** Constructs and initializes from an array */ 
    SquareMatrix(Real* array) : RectMatrix<Real, Dim, Dim>(array){
    }


    /** copy constructor */
    SquareMatrix(const RectMatrix<Real, Dim, Dim>& m) : RectMatrix<Real, Dim, Dim>(m) {
    }
            
    /** copy assignment operator */
    SquareMatrix<Real, Dim>& operator =(const RectMatrix<Real, Dim, Dim>& m) {
      RectMatrix<Real, Dim, Dim>::operator=(m);
      return *this;
    }
                                   
    /** Retunrs  an identity matrix*/

    static SquareMatrix<Real, Dim> identity() {
      SquareMatrix<Real, Dim> m;
                
      for (unsigned int i = 0; i < Dim; i++) 
        for (unsigned int j = 0; j < Dim; j++) 
          if (i == j)
            m(i, j) = 1.0;
          else
            m(i, j) = 0.0;

      return m;
    }

    /** 
     * Retunrs  the inversion of this matrix. 
     * @todo need implementation
     */
    SquareMatrix<Real, Dim>  inverse() {
      SquareMatrix<Real, Dim> result;

      return result;
    }        

    /**
     * Returns the determinant of this matrix.
     * @todo need implementation
     */
    Real determinant() const {
      Real det;
      return det;
    }
    
    /** Returns the trace of this matrix. */
    Real trace() const {
      Real tmp = 0;
               
      for (unsigned int i = 0; i < Dim ; i++)
        tmp += this->data_[i][i];

      return tmp;
    }
    
    /**
     * Returns the tensor contraction (double dot product) of two rank 2
     * tensors (or Matrices)
     * @param t1 first tensor
     * @param t2 second tensor
     * @return the tensor contraction (double dot product) of t1 and t2
     */
    Real doubleDot( const SquareMatrix<Real, Dim>& t1, const SquareMatrix<Real, Dim>& t2 ) {
      Real tmp;
      tmp = 0;
      
      for (unsigned int i = 0; i < Dim; i++)
        for (unsigned int j =0; j < Dim; j++)
          tmp += t1[i][j] * t2[i][j];
      
      return tmp;
    }


    /** Tests if this matrix is symmetrix. */            
    bool isSymmetric() const {
      for (unsigned int i = 0; i < Dim - 1; i++)
        for (unsigned int j = i; j < Dim; j++)
          if (fabs(this->data_[i][j] - this->data_[j][i]) > epsilon) 
            return false;
                        
      return true;
    }

    /** Tests if this matrix is orthogonal. */            
    bool isOrthogonal() {
      SquareMatrix<Real, Dim> tmp;

      tmp = *this * transpose();

      return tmp.isDiagonal();
    }

    /** Tests if this matrix is diagonal. */
    bool isDiagonal() const {
      for (unsigned int i = 0; i < Dim ; i++)
        for (unsigned int j = 0; j < Dim; j++)
          if (i !=j && fabs(this->data_[i][j]) > epsilon) 
            return false;
                        
      return true;
    }

    /** 
     * Returns a column vector that contains the elements from the
     * diagonal of m in the order R(0) = m(0,0), R(1) = m(1,1), and so
     * on.
     */
    Vector<Real, Dim> diagonals() const {
      Vector<Real, Dim> result;
      for (unsigned int i = 0; i < Dim; i++) {
        result(i) = this->data_[i][i];
      }
      return result;
    }

    /** Tests if this matrix is the unit matrix. */
    bool isUnitMatrix() const {
      if (!isDiagonal())
        return false;
                
      for (unsigned int i = 0; i < Dim ; i++)
        if (fabs(this->data_[i][i] - 1) > epsilon)
          return false;
                    
      return true;
    }         

    /** Return the transpose of this matrix */
    SquareMatrix<Real,  Dim> transpose() const{
      SquareMatrix<Real,  Dim> result;
                
      for (unsigned int i = 0; i < Dim; i++)
        for (unsigned int j = 0; j < Dim; j++)              
          result(j, i) = this->data_[i][j];

      return result;
    }
            
    /** @todo need implementation */
    void diagonalize() {
      //jacobi(m, eigenValues, ortMat);
    }

    /**
     * Jacobi iteration routines for computing eigenvalues/eigenvectors of 
     * real symmetric matrix
     *
     * @return true if success, otherwise return false
     * @param a symmetric matrix whose eigenvectors are to be computed. On return, the matrix is
     *     overwritten
     * @param d will contain the eigenvalues of the matrix On return of this function
     * @param v the columns of this matrix will contain the eigenvectors. The eigenvectors are 
     *    normalized and mutually orthogonal. 
     */
           
    static int jacobi(SquareMatrix<Real, Dim>& a, Vector<Real, Dim>& d, 
                      SquareMatrix<Real, Dim>& v);
  };//end SquareMatrix


  /*=========================================================================

  Program:   Visualization Toolkit
  Module:    $RCSfile: SquareMatrix.hpp,v $

  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.

  This software is distributed WITHOUT ANY WARRANTY; without even
  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  PURPOSE.  See the above copyright notice for more information.

  =========================================================================*/

#define VTK_ROTATE(a,i,j,k,l) g=a(i, j);h=a(k, l);a(i, j)=g-s*(h+g*tau); \
    a(k, l)=h+s*(g-h*tau)

#define VTK_MAX_ROTATIONS 20

  // Jacobi iteration for the solution of eigenvectors/eigenvalues of a nxn
  // real symmetric matrix. Square nxn matrix a; size of matrix in n;
  // output eigenvalues in w; and output eigenvectors in v. Resulting
  // eigenvalues/vectors are sorted in decreasing order; eigenvectors are
  // normalized.
  template<typename Real, int Dim>
  int SquareMatrix<Real, Dim>::jacobi(SquareMatrix<Real, Dim>& a, Vector<Real, Dim>& w, 
                                      SquareMatrix<Real, Dim>& v) {
    const int n = Dim;  
    int i, j, k, iq, ip, numPos;
    Real tresh, theta, tau, t, sm, s, h, g, c, tmp;
    Real bspace[4], zspace[4];
    Real *b = bspace;
    Real *z = zspace;

    // only allocate memory if the matrix is large
    if (n > 4) {
      b = new Real[n];
      z = new Real[n]; 
    }

    // initialize
    for (ip=0; ip<n; ip++) {
      for (iq=0; iq<n; iq++) {
        v(ip, iq) = 0.0;
      }
      v(ip, ip) = 1.0;
    }
    for (ip=0; ip<n; ip++) {
      b[ip] = w[ip] = a(ip, ip);
      z[ip] = 0.0;
    }

    // begin rotation sequence
    for (i=0; i<VTK_MAX_ROTATIONS; i++) {
      sm = 0.0;
      for (ip=0; ip<n-1; ip++) {
        for (iq=ip+1; iq<n; iq++) {
          sm += fabs(a(ip, iq));
        }
      }
      if (sm == 0.0) {
        break;
      }

      if (i < 3) {                                // first 3 sweeps
        tresh = 0.2*sm/(n*n);
      } else {
        tresh = 0.0;
      }

      for (ip=0; ip<n-1; ip++) {
        for (iq=ip+1; iq<n; iq++) {
          g = 100.0*fabs(a(ip, iq));

          // after 4 sweeps
          if (i > 3 && (fabs(w[ip])+g) == fabs(w[ip])
              && (fabs(w[iq])+g) == fabs(w[iq])) {
            a(ip, iq) = 0.0;
          } else if (fabs(a(ip, iq)) > tresh) {
            h = w[iq] - w[ip];
            if ( (fabs(h)+g) == fabs(h)) {
              t = (a(ip, iq)) / h;
            } else {
              theta = 0.5*h / (a(ip, iq));
              t = 1.0 / (fabs(theta)+sqrt(1.0+theta*theta));
              if (theta < 0.0) {
                t = -t;
              }
            }
            c = 1.0 / sqrt(1+t*t);
            s = t*c;
            tau = s/(1.0+c);
            h = t*a(ip, iq);
            z[ip] -= h;
            z[iq] += h;
            w[ip] -= h;
            w[iq] += h;
            a(ip, iq)=0.0;

            // ip already shifted left by 1 unit
            for (j = 0;j <= ip-1;j++) {
              VTK_ROTATE(a,j,ip,j,iq);
            }
            // ip and iq already shifted left by 1 unit
            for (j = ip+1;j <= iq-1;j++) {
              VTK_ROTATE(a,ip,j,j,iq);
            }
            // iq already shifted left by 1 unit
            for (j=iq+1; j<n; j++) {
              VTK_ROTATE(a,ip,j,iq,j);
            }
            for (j=0; j<n; j++) {
              VTK_ROTATE(v,j,ip,j,iq);
            }
          }
        }
      }

      for (ip=0; ip<n; ip++) {
        b[ip] += z[ip];
        w[ip] = b[ip];
        z[ip] = 0.0;
      }
    }

    //// this is NEVER called
    if ( i >= VTK_MAX_ROTATIONS ) {
      std::cout << "vtkMath::Jacobi: Error extracting eigenfunctions" << std::endl;
      if (n > 4) {
        delete[] b;
        delete[] z;
      }      
      return 0;
    }

    // sort eigenfunctions                 these changes do not affect accuracy 
    for (j=0; j<n-1; j++) {                  // boundary incorrect
      k = j;
      tmp = w[k];
      for (i=j+1; i<n; i++) {                // boundary incorrect, shifted already
        if (w[i] >= tmp) {                   // why exchage if same?
          k = i;
          tmp = w[k];
        }
      }
      if (k != j) {
        w[k] = w[j];
        w[j] = tmp;
        for (i=0; i<n; i++) {
          tmp = v(i, j);
          v(i, j) = v(i, k);
          v(i, k) = tmp;
        }
      }
    }
    // insure eigenvector consistency (i.e., Jacobi can compute vectors that
    // are negative of one another (.707,.707,0) and (-.707,-.707,0). This can
    // reek havoc in hyperstreamline/other stuff. We will select the most
    // positive eigenvector.
    int ceil_half_n = (n >> 1) + (n & 1);
    for (j=0; j<n; j++) {
      for (numPos=0, i=0; i<n; i++) {
        if ( v(i, j) >= 0.0 ) {
          numPos++;
        }
      }
      //    if ( numPos < ceil(RealType(n)/RealType(2.0)) )
      if ( numPos < ceil_half_n) {
        for (i=0; i<n; i++) {
          v(i, j) *= -1.0;
        }
      }
    }

    if (n > 4) {
      delete [] b;
      delete [] z;
    }
    return 1;
  }


  typedef SquareMatrix<RealType, 6> Mat6x6d;
}
#endif //MATH_SQUAREMATRIX_HPP 

Revision:	1874
Committed:	Wed May 15 15:09:35 2013 UTC (11 years, 11 months ago) by gezelter
File size:	12393 byte(s)
Log Message:	Fixed a bunch of cppcheck warnings.
#	User	Rev	Content
1	gezelter	507	/*
2	gezelter	246	* Copyright (c) 2005 The University of Notre Dame. All Rights Reserved.
3	tim	70	*
4	gezelter	246	* The University of Notre Dame grants you ("Licensee") a
5			* non-exclusive, royalty free, license to use, modify and
6			* redistribute this software in source and binary code form, provided
7			* that the following conditions are met:
8			*
9	gezelter	1390	* 1. Redistributions of source code must retain the above copyright
10	gezelter	246	* notice, this list of conditions and the following disclaimer.
11			*
12	gezelter	1390	* 2. Redistributions in binary form must reproduce the above copyright
13	gezelter	246	* notice, this list of conditions and the following disclaimer in the
14			* documentation and/or other materials provided with the
15			* distribution.
16			*
17			* This software is provided "AS IS," without a warranty of any
18			* kind. All express or implied conditions, representations and
19			* warranties, including any implied warranty of merchantability,
20			* fitness for a particular purpose or non-infringement, are hereby
21			* excluded. The University of Notre Dame and its licensors shall not
22			* be liable for any damages suffered by licensee as a result of
23			* using, modifying or distributing the software or its
24			* derivatives. In no event will the University of Notre Dame or its
25			* licensors be liable for any lost revenue, profit or data, or for
26			* direct, indirect, special, consequential, incidental or punitive
27			* damages, however caused and regardless of the theory of liability,
28			* arising out of the use of or inability to use software, even if the
29			* University of Notre Dame has been advised of the possibility of
30			* such damages.
31	gezelter	1390	*
32			* SUPPORT OPEN SCIENCE! If you use OpenMD or its source code in your
33			* research, please cite the appropriate papers when you publish your
34			* work. Good starting points are:
35			*
36			* [1] Meineke, et al., J. Comp. Chem. 26, 252-271 (2005).
37			* [2] Fennell & Gezelter, J. Chem. Phys. 124, 234104 (2006).
38	gezelter	1850	* [3] Sun, Lin & Gezelter, J. Chem. Phys. 128, 234107 (2008).
39	gezelter	1665	* [4] Kuang & Gezelter, J. Chem. Phys. 133, 164101 (2010).
40			* [5] Vardeman, Stocker & Gezelter, J. Chem. Theory Comput. 7, 834 (2011).
41	tim	70	*/
42	gezelter	246
43	tim	70	/**
44			* @file SquareMatrix.hpp
45			* @author Teng Lin
46			* @date 10/11/2004
47			* @version 1.0
48			*/
49	gezelter	507	#ifndef MATH_SQUAREMATRIX_HPP
50	tim	70	#define MATH_SQUAREMATRIX_HPP
51
52	tim	74	#include "math/RectMatrix.hpp"
53	gezelter	956	#include "utils/NumericConstant.hpp"
54	tim	70
55	gezelter	1390	namespace OpenMD {
56	tim	70
57	gezelter	507	/**
58			* @class SquareMatrix SquareMatrix.hpp "math/SquareMatrix.hpp"
59			* @brief A square matrix class
60	gezelter	1808	* \tparam Real the element type
61			* \tparam Dim the dimension of the square matrix
62	gezelter	507	*/
63			template<typename Real, int Dim>
64			class SquareMatrix : public RectMatrix<Real, Dim, Dim> {
65			public:
66			typedef Real ElemType;
67			typedef Real* ElemPoinerType;
68	tim	70
69	gezelter	507	/** default constructor */
70			SquareMatrix() {
71			for (unsigned int i = 0; i < Dim; i++)
72			for (unsigned int j = 0; j < Dim; j++)
73			this->data_[i][j] = 0.0;
74			}
75	tim	70
76	gezelter	507	/** Constructs and initializes every element of this matrix to a scalar */
77			SquareMatrix(Real s) : RectMatrix<Real, Dim, Dim>(s){
78			}
79	tim	151
80	gezelter	507	/** Constructs and initializes from an array */
81			SquareMatrix(Real* array) : RectMatrix<Real, Dim, Dim>(array){
82			}
83	tim	151
84
85	gezelter	507	/** copy constructor */
86			SquareMatrix(const RectMatrix<Real, Dim, Dim>& m) : RectMatrix<Real, Dim, Dim>(m) {
87			}
88	tim	70
89	gezelter	507	/** copy assignment operator */
90			SquareMatrix<Real, Dim>& operator =(const RectMatrix<Real, Dim, Dim>& m) {
91			RectMatrix<Real, Dim, Dim>::operator=(m);
92			return *this;
93			}
94	tim	137
95	gezelter	507	/** Retunrs an identity matrix*/
96	tim	74
97	gezelter	507	static SquareMatrix<Real, Dim> identity() {
98			SquareMatrix<Real, Dim> m;
99	tim	137
100	gezelter	507	for (unsigned int i = 0; i < Dim; i++)
101			for (unsigned int j = 0; j < Dim; j++)
102			if (i == j)
103			m(i, j) = 1.0;
104			else
105			m(i, j) = 0.0;
106	tim	70
107	gezelter	507	return m;
108			}
109	tim	74
110	gezelter	507	/**
111			* Retunrs the inversion of this matrix.
112			* @todo need implementation
113			*/
114			SquareMatrix<Real, Dim> inverse() {
115			SquareMatrix<Real, Dim> result;
116	tim	70
117	gezelter	507	return result;
118			}
119	tim	70
120	gezelter	507	/**
121			* Returns the determinant of this matrix.
122			* @todo need implementation
123			*/
124			Real determinant() const {
125			Real det;
126			return det;
127			}
128	gezelter	1808
129	gezelter	507	/** Returns the trace of this matrix. */
130			Real trace() const {
131			Real tmp = 0;
132	tim	137
133	gezelter	507	for (unsigned int i = 0; i < Dim ; i++)
134			tmp += this->data_[i][i];
135	tim	70
136	gezelter	507	return tmp;
137			}
138	gezelter	1753
139			/**
140			* Returns the tensor contraction (double dot product) of two rank 2
141			* tensors (or Matrices)
142			* @param t1 first tensor
143			* @param t2 second tensor
144			* @return the tensor contraction (double dot product) of t1 and t2
145			*/
146			Real doubleDot( const SquareMatrix<Real, Dim>& t1, const SquareMatrix<Real, Dim>& t2 ) {
147			Real tmp;
148			tmp = 0;
149
150			for (unsigned int i = 0; i < Dim; i++)
151			for (unsigned int j =0; j < Dim; j++)
152			tmp += t1[i][j] * t2[i][j];
153
154			return tmp;
155			}
156	tim	70
157	gezelter	1794
158	gezelter	507	/** Tests if this matrix is symmetrix. */
159			bool isSymmetric() const {
160			for (unsigned int i = 0; i < Dim - 1; i++)
161			for (unsigned int j = i; j < Dim; j++)
162	gezelter	956	if (fabs(this->data_[i][j] - this->data_[j][i]) > epsilon)
163	gezelter	507	return false;
164	tim	137
165	gezelter	507	return true;
166			}
167	tim	70
168	gezelter	507	/** Tests if this matrix is orthogonal. */
169			bool isOrthogonal() {
170			SquareMatrix<Real, Dim> tmp;
171	tim	70
172	gezelter	507	tmp = this transpose();
173	tim	70
174	gezelter	507	return tmp.isDiagonal();
175			}
176	tim	70
177	gezelter	507	/** Tests if this matrix is diagonal. */
178			bool isDiagonal() const {
179			for (unsigned int i = 0; i < Dim ; i++)
180			for (unsigned int j = 0; j < Dim; j++)
181	gezelter	956	if (i !=j && fabs(this->data_[i][j]) > epsilon)
182	gezelter	507	return false;
183	tim	137
184	gezelter	507	return true;
185			}
186	tim	137
187	gezelter	1760	/**
188			* Returns a column vector that contains the elements from the
189			* diagonal of m in the order R(0) = m(0,0), R(1) = m(1,1), and so
190			* on.
191			*/
192			Vector<Real, Dim> diagonals() const {
193			Vector<Real, Dim> result;
194			for (unsigned int i = 0; i < Dim; i++) {
195			result(i) = this->data_[i][i];
196			}
197			return result;
198			}
199
200	gezelter	507	/** Tests if this matrix is the unit matrix. */
201			bool isUnitMatrix() const {
202			if (!isDiagonal())
203			return false;
204	tim	70
205	gezelter	507	for (unsigned int i = 0; i < Dim ; i++)
206	gezelter	956	if (fabs(this->data_[i][i] - 1) > epsilon)
207	gezelter	507	return false;
208	tim	137
209	gezelter	507	return true;
210			}
211	tim	70
212	gezelter	507	/** Return the transpose of this matrix */
213			SquareMatrix<Real, Dim> transpose() const{
214			SquareMatrix<Real, Dim> result;
215	tim	273
216	gezelter	507	for (unsigned int i = 0; i < Dim; i++)
217			for (unsigned int j = 0; j < Dim; j++)
218			result(j, i) = this->data_[i][j];
219	tim	273
220	gezelter	507	return result;
221			}
222	tim	273
223	gezelter	507	/** @todo need implementation */
224			void diagonalize() {
225			//jacobi(m, eigenValues, ortMat);
226			}
227	tim	76
228	gezelter	507	/**
229			* Jacobi iteration routines for computing eigenvalues/eigenvectors of
230			* real symmetric matrix
231			*
232			* @return true if success, otherwise return false
233			* @param a symmetric matrix whose eigenvectors are to be computed. On return, the matrix is
234			* overwritten
235	gezelter	1808	* @param d will contain the eigenvalues of the matrix On return of this function
236	gezelter	507	* @param v the columns of this matrix will contain the eigenvectors. The eigenvectors are
237			* normalized and mutually orthogonal.
238			*/
239	tim	137
240	gezelter	507	static int jacobi(SquareMatrix<Real, Dim>& a, Vector<Real, Dim>& d,
241			SquareMatrix<Real, Dim>& v);
242			};//end SquareMatrix
243	tim	70
244	tim	76
245	gezelter	507	/*=========================================================================
246	tim	76
247	tim	123	Program: Visualization Toolkit
248			Module: $RCSfile: SquareMatrix.hpp,v $
249	tim	76
250	tim	123	Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
251			All rights reserved.
252			See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
253
254	gezelter	507	This software is distributed WITHOUT ANY WARRANTY; without even
255			the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
256			PURPOSE. See the above copyright notice for more information.
257	tim	123
258	gezelter	507	=========================================================================*/
259	tim	123
260	gezelter	507	#define VTK_ROTATE(a,i,j,k,l) g=a(i, j);h=a(k, l);a(i, j)=g-s(h+gtau); \
261			a(k, l)=h+s(g-htau)
262	tim	123
263			#define VTK_MAX_ROTATIONS 20
264
265	gezelter	507	// Jacobi iteration for the solution of eigenvectors/eigenvalues of a nxn
266			// real symmetric matrix. Square nxn matrix a; size of matrix in n;
267			// output eigenvalues in w; and output eigenvectors in v. Resulting
268			// eigenvalues/vectors are sorted in decreasing order; eigenvectors are
269			// normalized.
270			template<typename Real, int Dim>
271			int SquareMatrix<Real, Dim>::jacobi(SquareMatrix<Real, Dim>& a, Vector<Real, Dim>& w,
272			SquareMatrix<Real, Dim>& v) {
273			const int n = Dim;
274			int i, j, k, iq, ip, numPos;
275			Real tresh, theta, tau, t, sm, s, h, g, c, tmp;
276			Real bspace[4], zspace[4];
277			Real *b = bspace;
278			Real *z = zspace;
279	tim	123
280	gezelter	507	// only allocate memory if the matrix is large
281			if (n > 4) {
282			b = new Real[n];
283			z = new Real[n];
284			}
285	tim	123
286	gezelter	507	// initialize
287			for (ip=0; ip<n; ip++) {
288			for (iq=0; iq<n; iq++) {
289			v(ip, iq) = 0.0;
290			}
291			v(ip, ip) = 1.0;
292			}
293			for (ip=0; ip<n; ip++) {
294			b[ip] = w[ip] = a(ip, ip);
295			z[ip] = 0.0;
296			}
297	tim	76
298	gezelter	507	// begin rotation sequence
299			for (i=0; i<VTK_MAX_ROTATIONS; i++) {
300			sm = 0.0;
301			for (ip=0; ip<n-1; ip++) {
302			for (iq=ip+1; iq<n; iq++) {
303			sm += fabs(a(ip, iq));
304			}
305			}
306			if (sm == 0.0) {
307			break;
308			}
309	tim	76
310	gezelter	507	if (i < 3) { // first 3 sweeps
311			tresh = 0.2sm/(nn);
312			} else {
313			tresh = 0.0;
314			}
315	tim	76
316	gezelter	507	for (ip=0; ip<n-1; ip++) {
317			for (iq=ip+1; iq<n; iq++) {
318			g = 100.0*fabs(a(ip, iq));
319	tim	76
320	gezelter	507	// after 4 sweeps
321			if (i > 3 && (fabs(w[ip])+g) == fabs(w[ip])
322			&& (fabs(w[iq])+g) == fabs(w[iq])) {
323			a(ip, iq) = 0.0;
324			} else if (fabs(a(ip, iq)) > tresh) {
325			h = w[iq] - w[ip];
326			if ( (fabs(h)+g) == fabs(h)) {
327			t = (a(ip, iq)) / h;
328			} else {
329			theta = 0.5*h / (a(ip, iq));
330			t = 1.0 / (fabs(theta)+sqrt(1.0+theta*theta));
331			if (theta < 0.0) {
332			t = -t;
333			}
334			}
335			c = 1.0 / sqrt(1+t*t);
336			s = t*c;
337			tau = s/(1.0+c);
338			h = t*a(ip, iq);
339			z[ip] -= h;
340			z[iq] += h;
341			w[ip] -= h;
342			w[iq] += h;
343			a(ip, iq)=0.0;
344	tim	76
345	gezelter	507	// ip already shifted left by 1 unit
346			for (j = 0;j <= ip-1;j++) {
347			VTK_ROTATE(a,j,ip,j,iq);
348			}
349			// ip and iq already shifted left by 1 unit
350			for (j = ip+1;j <= iq-1;j++) {
351			VTK_ROTATE(a,ip,j,j,iq);
352			}
353			// iq already shifted left by 1 unit
354			for (j=iq+1; j<n; j++) {
355			VTK_ROTATE(a,ip,j,iq,j);
356			}
357			for (j=0; j<n; j++) {
358			VTK_ROTATE(v,j,ip,j,iq);
359			}
360			}
361			}
362			}
363	tim	93
364	gezelter	507	for (ip=0; ip<n; ip++) {
365			b[ip] += z[ip];
366			w[ip] = b[ip];
367			z[ip] = 0.0;
368			}
369			}
370	tim	93
371	gezelter	507	//// this is NEVER called
372			if ( i >= VTK_MAX_ROTATIONS ) {
373			std::cout << "vtkMath::Jacobi: Error extracting eigenfunctions" << std::endl;
374	gezelter	1874	if (n > 4) {
375			delete[] b;
376			delete[] z;
377			}
378	gezelter	507	return 0;
379			}
380	tim	76
381	gezelter	507	// sort eigenfunctions these changes do not affect accuracy
382			for (j=0; j<n-1; j++) { // boundary incorrect
383			k = j;
384			tmp = w[k];
385			for (i=j+1; i<n; i++) { // boundary incorrect, shifted already
386			if (w[i] >= tmp) { // why exchage if same?
387			k = i;
388			tmp = w[k];
389			}
390			}
391			if (k != j) {
392			w[k] = w[j];
393			w[j] = tmp;
394			for (i=0; i<n; i++) {
395			tmp = v(i, j);
396			v(i, j) = v(i, k);
397			v(i, k) = tmp;
398			}
399			}
400			}
401			// insure eigenvector consistency (i.e., Jacobi can compute vectors that
402			// are negative of one another (.707,.707,0) and (-.707,-.707,0). This can
403			// reek havoc in hyperstreamline/other stuff. We will select the most
404			// positive eigenvector.
405			int ceil_half_n = (n >> 1) + (n & 1);
406			for (j=0; j<n; j++) {
407			for (numPos=0, i=0; i<n; i++) {
408			if ( v(i, j) >= 0.0 ) {
409			numPos++;
410			}
411			}
412	tim	963	// if ( numPos < ceil(RealType(n)/RealType(2.0)) )
413	gezelter	507	if ( numPos < ceil_half_n) {
414			for (i=0; i<n; i++) {
415			v(i, j) *= -1.0;
416			}
417			}
418			}
419	tim	76
420	gezelter	507	if (n > 4) {
421			delete [] b;
422			delete [] z;
423	tim	76	}
424	gezelter	507	return 1;
425			}
426	tim	76
427
428	tim	963	typedef SquareMatrix<RealType, 6> Mat6x6d;
429	tim	76	}
430	tim	123	#endif //MATH_SQUAREMATRIX_HPP
431	tim	76