Another set of UI messages fixes and tweaks! No functional changes.
[blender.git] / extern / Eigen3 / Eigen / src / Core / StableNorm.h
1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra.
3 //
4 // Copyright (C) 2009 Gael Guennebaud <gael.guennebaud@inria.fr>
5 //
6 // Eigen is free software; you can redistribute it and/or
7 // modify it under the terms of the GNU Lesser General Public
8 // License as published by the Free Software Foundation; either
9 // version 3 of the License, or (at your option) any later version.
10 //
11 // Alternatively, you can redistribute it and/or
12 // modify it under the terms of the GNU General Public License as
13 // published by the Free Software Foundation; either version 2 of
14 // the License, or (at your option) any later version.
15 //
16 // Eigen is distributed in the hope that it will be useful, but WITHOUT ANY
17 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18 // FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the
19 // GNU General Public License for more details.
20 //
21 // You should have received a copy of the GNU Lesser General Public
22 // License and a copy of the GNU General Public License along with
23 // Eigen. If not, see <http://www.gnu.org/licenses/>.
24
25 #ifndef EIGEN_STABLENORM_H
26 #define EIGEN_STABLENORM_H
27
28 namespace internal {
29 template<typename ExpressionType, typename Scalar>
30 inline void stable_norm_kernel(const ExpressionType& bl, Scalar& ssq, Scalar& scale, Scalar& invScale)
31 {
32   Scalar max = bl.cwiseAbs().maxCoeff();
33   if (max>scale)
34   {
35     ssq = ssq * abs2(scale/max);
36     scale = max;
37     invScale = Scalar(1)/scale;
38   }
39   // TODO if the max is much much smaller than the current scale,
40   // then we can neglect this sub vector
41   ssq += (bl*invScale).squaredNorm();
42 }
43 }
44
45 /** \returns the \em l2 norm of \c *this avoiding underflow and overflow.
46   * This version use a blockwise two passes algorithm:
47   *  1 - find the absolute largest coefficient \c s
48   *  2 - compute \f$ s \Vert \frac{*this}{s} \Vert \f$ in a standard way
49   *
50   * For architecture/scalar types supporting vectorization, this version
51   * is faster than blueNorm(). Otherwise the blueNorm() is much faster.
52   *
53   * \sa norm(), blueNorm(), hypotNorm()
54   */
55 template<typename Derived>
56 inline typename NumTraits<typename internal::traits<Derived>::Scalar>::Real
57 MatrixBase<Derived>::stableNorm() const
58 {
59   using std::min;
60   const Index blockSize = 4096;
61   RealScalar scale = 0;
62   RealScalar invScale = 1;
63   RealScalar ssq = 0; // sum of square
64   enum {
65     Alignment = (int(Flags)&DirectAccessBit) || (int(Flags)&AlignedBit) ? 1 : 0
66   };
67   Index n = size();
68   Index bi = internal::first_aligned(derived());
69   if (bi>0)
70     internal::stable_norm_kernel(this->head(bi), ssq, scale, invScale);
71   for (; bi<n; bi+=blockSize)
72     internal::stable_norm_kernel(this->segment(bi,(min)(blockSize, n - bi)).template forceAlignedAccessIf<Alignment>(), ssq, scale, invScale);
73   return scale * internal::sqrt(ssq);
74 }
75
76 /** \returns the \em l2 norm of \c *this using the Blue's algorithm.
77   * A Portable Fortran Program to Find the Euclidean Norm of a Vector,
78   * ACM TOMS, Vol 4, Issue 1, 1978.
79   *
80   * For architecture/scalar types without vectorization, this version
81   * is much faster than stableNorm(). Otherwise the stableNorm() is faster.
82   *
83   * \sa norm(), stableNorm(), hypotNorm()
84   */
85 template<typename Derived>
86 inline typename NumTraits<typename internal::traits<Derived>::Scalar>::Real
87 MatrixBase<Derived>::blueNorm() const
88 {
89   using std::pow;
90   using std::min;
91   using std::max;
92   static Index nmax = -1;
93   static RealScalar b1, b2, s1m, s2m, overfl, rbig, relerr;
94   if(nmax <= 0)
95   {
96     int nbig, ibeta, it, iemin, iemax, iexp;
97     RealScalar abig, eps;
98     // This program calculates the machine-dependent constants
99     // bl, b2, slm, s2m, relerr overfl, nmax
100     // from the "basic" machine-dependent numbers
101     // nbig, ibeta, it, iemin, iemax, rbig.
102     // The following define the basic machine-dependent constants.
103     // For portability, the PORT subprograms "ilmaeh" and "rlmach"
104     // are used. For any specific computer, each of the assignment
105     // statements can be replaced
106     nbig  = (std::numeric_limits<Index>::max)();            // largest integer
107     ibeta = std::numeric_limits<RealScalar>::radix;         // base for floating-point numbers
108     it    = std::numeric_limits<RealScalar>::digits;        // number of base-beta digits in mantissa
109     iemin = std::numeric_limits<RealScalar>::min_exponent;  // minimum exponent
110     iemax = std::numeric_limits<RealScalar>::max_exponent;  // maximum exponent
111     rbig  = (std::numeric_limits<RealScalar>::max)();         // largest floating-point number
112
113     iexp  = -((1-iemin)/2);
114     b1    = RealScalar(pow(RealScalar(ibeta),RealScalar(iexp)));  // lower boundary of midrange
115     iexp  = (iemax + 1 - it)/2;
116     b2    = RealScalar(pow(RealScalar(ibeta),RealScalar(iexp)));   // upper boundary of midrange
117
118     iexp  = (2-iemin)/2;
119     s1m   = RealScalar(pow(RealScalar(ibeta),RealScalar(iexp)));   // scaling factor for lower range
120     iexp  = - ((iemax+it)/2);
121     s2m   = RealScalar(pow(RealScalar(ibeta),RealScalar(iexp)));   // scaling factor for upper range
122
123     overfl  = rbig*s2m;             // overflow boundary for abig
124     eps     = RealScalar(pow(double(ibeta), 1-it));
125     relerr  = internal::sqrt(eps);         // tolerance for neglecting asml
126     abig    = RealScalar(1.0/eps - 1.0);
127     if (RealScalar(nbig)>abig)  nmax = int(abig);  // largest safe n
128     else                        nmax = nbig;
129   }
130   Index n = size();
131   RealScalar ab2 = b2 / RealScalar(n);
132   RealScalar asml = RealScalar(0);
133   RealScalar amed = RealScalar(0);
134   RealScalar abig = RealScalar(0);
135   for(Index j=0; j<n; ++j)
136   {
137     RealScalar ax = internal::abs(coeff(j));
138     if(ax > ab2)     abig += internal::abs2(ax*s2m);
139     else if(ax < b1) asml += internal::abs2(ax*s1m);
140     else             amed += internal::abs2(ax);
141   }
142   if(abig > RealScalar(0))
143   {
144     abig = internal::sqrt(abig);
145     if(abig > overfl)
146     {
147       eigen_assert(false && "overflow");
148       return rbig;
149     }
150     if(amed > RealScalar(0))
151     {
152       abig = abig/s2m;
153       amed = internal::sqrt(amed);
154     }
155     else
156       return abig/s2m;
157   }
158   else if(asml > RealScalar(0))
159   {
160     if (amed > RealScalar(0))
161     {
162       abig = internal::sqrt(amed);
163       amed = internal::sqrt(asml) / s1m;
164     }
165     else
166       return internal::sqrt(asml)/s1m;
167   }
168   else
169     return internal::sqrt(amed);
170   asml = (min)(abig, amed);
171   abig = (max)(abig, amed);
172   if(asml <= abig*relerr)
173     return abig;
174   else
175     return abig * internal::sqrt(RealScalar(1) + internal::abs2(asml/abig));
176 }
177
178 /** \returns the \em l2 norm of \c *this avoiding undeflow and overflow.
179   * This version use a concatenation of hypot() calls, and it is very slow.
180   *
181   * \sa norm(), stableNorm()
182   */
183 template<typename Derived>
184 inline typename NumTraits<typename internal::traits<Derived>::Scalar>::Real
185 MatrixBase<Derived>::hypotNorm() const
186 {
187   return this->cwiseAbs().redux(internal::scalar_hypot_op<RealScalar>());
188 }
189
190 #endif // EIGEN_STABLENORM_H