commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l..@apache.org
Subject svn commit: r653925 - in /commons/sandbox/nabla/trunk/src/site: site.xml xdoc/singularities.xml
Date Tue, 06 May 2008 21:11:56 GMT
Author: luc
Date: Tue May  6 14:11:54 2008
New Revision: 653925

URL: http://svn.apache.org/viewvc?rev=653925&view=rev
Log:
added a specific documentation page to explain singularities handling

Added:
    commons/sandbox/nabla/trunk/src/site/xdoc/singularities.xml   (with props)
Modified:
    commons/sandbox/nabla/trunk/src/site/site.xml

Modified: commons/sandbox/nabla/trunk/src/site/site.xml
URL: http://svn.apache.org/viewvc/commons/sandbox/nabla/trunk/src/site/site.xml?rev=653925&r1=653924&r2=653925&view=diff
==============================================================================
--- commons/sandbox/nabla/trunk/src/site/site.xml (original)
+++ commons/sandbox/nabla/trunk/src/site/site.xml Tue May  6 14:11:54 2008
@@ -22,9 +22,10 @@
   </bannerRight>
   <body>
     <menu name="Nabla">
-      <item name="Overview"  href="/index.html" />
-      <item name="Usage"     href="/usage.html" />
-      <item name="Internals" href="/internals.html" />
+      <item name="Overview"      href="/index.html" />
+      <item name="Usage"         href="/usage.html" />
+      <item name="Internals"     href="/internals.html" />
+      <item name="Singularities" href="/singularities.html" />
     </menu>
     <menu name="Development">
       <item name="Mailing Lists"           href="/mail-lists.html"/>

Added: commons/sandbox/nabla/trunk/src/site/xdoc/singularities.xml
URL: http://svn.apache.org/viewvc/commons/sandbox/nabla/trunk/src/site/xdoc/singularities.xml?rev=653925&view=auto
==============================================================================
--- commons/sandbox/nabla/trunk/src/site/xdoc/singularities.xml (added)
+++ commons/sandbox/nabla/trunk/src/site/xdoc/singularities.xml Tue May  6 14:11:54 2008
@@ -0,0 +1,283 @@
+<?xml version="1.0" encoding="UTF-8" ?>
+<!--
+   Licensed to the Apache Software Foundation (ASF) under one or more
+   contributor license agreements.  See the NOTICE file distributed with
+   this work for additional information regarding copyright ownership.
+   The ASF licenses this file to You under the Apache License, Version 2.0
+   (the "License"); you may not use this file except in compliance with
+   the License.  You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+-->
+
+<document>
+
+  <properties>
+    <title>Singularities handling</title>
+  </properties>
+
+  <body>
+    <section name="Singularities">
+
+      <subsection name="Overview">
+        <p>
+          The derivatives produced by Nabla are computed by applying
+          the exact differentiation rules to the various
+          sub-expressions encountered while evaluating the function.
+          The function to differentiate may contain conditional or
+          discontinuous statements like <code>if/then/else</code>
+          constructs, calls to the <code>Math.floor()</code> method,
+          or use of the <code>%</code> operator. From now on, we will
+          call <em>branching points</em> the values of the
+          <code>t</code> parameter that trigger changes in these
+          statements.
+        </p>
+
+        <p>
+          By construction, the derivatives produced by Nabla have the
+          same branching points as the initial function. The overall
+          structure of the code is similar in both functions, the only
+          differences being that the embedded mathematical expressions
+          are differentiated in one case and not in the other case.
+        </p>
+
+        <p>
+          Consider a value <code>t<sub>0</sub></code> which is
+          <em>not</em> at a branching point. For small variations of
+          the <code>t</code> value within <code>t<sub>0</sub></code>
+          neighborhood, the same sub-expressions will be encountered
+          during derivative evaluations and the derivative will be
+          continuous. This is true even if the point is very close to
+          a branching point, as long as it is not exactly on it. This
+          behavior is more robust than what occurs with finite
+          differences schemes because these schemes involve several
+          evaluations of the function at separate points. If a finite
+          differences scheme is evaluated too close from a branching
+          point, the evaluations may be dispersed on both sides of it,
+          leading to invalid results or computation errors.
+        </p>
+
+        <p>
+          Consider a value <code>t<sub>0</sub></code> which is
+          <em>exactly</em> at a branching point. Depending on the way
+          the conditional or discontinuous statement is written, one of
+          the branch is followed and the derivative is computed as if
+          this branch were valid not only at the point itself but also in
+          its neighborhood.
+        </p>
+
+        <p>
+          In a sense Nabla extends the validity of a derivative from the
+          interior of a domain to its boundary.
+        </p>
+      </subsection>
+
+      <subsection name="Example">
+        <p>
+          The following example shows a branching point for a simple
+          conditional statement.
+        </p>
+
+        <source>
+          UnivariateDifferentiable singular = new UnivariateDifferentiable() {
+              public double f(double t) {
+                  if (t &lt; 0) {
+                      return 2 * t;
+                  } else {
+                      return 3 * t;
+                  }
+              }
+          };
+        </source>
+
+        <p>
+          In this example, there is one branching point at <code>t =
+          0</code>. When the parameter <code>t</code> is away from 0,
+          the derivative is either 2 (for negative <code>t</code>) or
+          3 (for positive <code>t</code>).  When the parameter
+          <code>t</code> is exactly 0, the branch which will be 
+          elected is the <code>else</code> branch, so the derivative
+          with respect to <code>t</code> will be set to 3, just as if
+          the parameter were positive. The validity domain of the
+          derivative as computed by Nabla is extended, it contains the
+          boundary value 0.
+        </p>
+
+        <p>
+          This however is not the true mathematical derivative since the
+          function is <em>not</em> differentiable at <code>t = 0</code>.
+          It does have a left derivative and a right derivative, but
+          since they are different there are no global derivatives at
+          this point.
+        </p>
+
+        <p>
+          We can see the reason why from a purely mathematical standpoint
+          the function is considered not to be differentiable at this
+          point. If we change the <code>if (t &lt; 0)</code> statement into
+          <code>if (t &lt;= 0)</code>, the value of the primitive function
+          does not change at all (both <code>2 * 0</code> and <code>3 *
+          0</code> produce <code>0</code>), but the value of the derivative
+          as computed by Nabla becomes 2. 
+        </p>
+
+        <p>
+          The following example is only slightly different from the previous
+          one. However, it will lead to different results.
+        </p>
+
+        <source>
+          UnivariateDifferentiable nonSingular = new UnivariateDifferentiable() {
+              public double f(double t) {
+                  if (t &lt; 0) {
+                      return 2 * t * t;
+                  } else {
+                      return 3 * t * t;
+                  }
+              }
+          };
+        </source>
+
+        <p>
+          In this example, the derivatives computed in both branches share the
+          same value, which is 0. So the function <em>is</em> differentiable
+          and the value computed by Nabla is the real derivative. Changing the
+          <code>if (t &lt; 0)</code> statement into <code>if (t &lt;=
0)</code>
+          does not invalidate this result.
+        </p>
+
+        <p>
+          Nabla does not detect branching points. It inherits this behavior from
+          the initial function which does neither keep track of all the
+          conditionals it encounters during its evaluation nor distinguishes
+          conditionals largely met from conditionals almost missed.
+        </p>
+
+        <p>
+          In summary:
+          <ul>
+            <li>
+              Nabla produces derivatives at branching points,
+            </li> 
+            <li>
+              if the mathematical derivative exists at a branching point,
+              Nabla computes it normally,
+            </li>
+            <li>
+              if the mathematical derivative does not exists, Nabla computes
+              a value by extending the domain of validity of one of the
+              branches,
+            </li>
+            <li>
+              there is no special handling of branching points.
+            </li>
+          </ul>
+        </p>
+
+      </subsection>
+
+      <subsection name="Rationale">
+        <p>
+          The design choice to let Nabla compute derivatives at branching points
+          where the function is not differentiable may seem strange. However,
+          there are several good reasons to do this.
+        </p>
+
+        <dl>
+          <dt>Complexity</dt>
+          <dd>
+            <p>
+              Detecting singularities and handling them properly would
+              be very difficult.We would need to check each conditional
+              and see if we are exactly at its cut point or not, and if
+              the derivatives on both sides are equal or not. This
+              implies we would have to compute the derivatives from
+              both branches in parallel and reconcile the results at the
+              end. If the derivatives on both sides are equal, then the
+              function is differentiable and we have its value. If the
+              values are not equal, then the function is not
+              differentiable and an error case should be triggered
+              (either setting the derivative to <code>Double.NaN</code>
+              or throwing an <code>InvalidArgumentexception</code>).
+            </p>
+
+            <p>
+              Considering each branch can itself be split into two
+              other branches which can themselves be split furthre and
+              so on, this is a very tough design to implement.
+            </p>
+
+            <p>
+
+              Blindly assuming a function is not differentiable simply
+              because it has a conditional is not acceptable. The
+              last example above is an example of this.
+            </p>
+          </dd>
+
+          <dt>Performance</dt>
+          <dd>
+            <p>
+              The second reason is that if such a complete handling of
+              cut points were implemented, it would have a very bad
+              impact on performance. The number of conditionals
+              evaluations would be doubled (adding an equality test to
+              the existing inequality ones). In addition, when branching
+              points are encountered, the complete computation would be
+              performed on both branches. Given that physical models
+              often only have a few specific cut points that repeat
+              throughout the code (0 being by far the most important
+              one for many functions), and that conditional constructs
+              may appear inside loops that may iterate hundreds or
+              thousands of times, it is clear than the computation can
+              be put to an halt by such thorough branches explorations.
+            </p>
+          </dd>
+
+          <dt>Needs</dt>
+          <dd>
+            <p>
+              The third reason is simply that the pure mathematical
+              compliance is not always desired.
+            </p>
+
+            <p>
+              An important family of singularities corresponds to
+              domains boundaries: on one side the computation can be
+              done and on the other side it cannot, either due to
+              mathematical problems (square roots, logarithms, arc
+              sines ...) or physical problems (collision, null
+              pressure, phase change ...). In these cases, there is
+              only one branch that leads to a result, the other one
+              leading to an error. If the computation <em>can</em> be
+              realized on the cut point itself, what we really want is
+              to have a derivative that is consistent with the side
+              from which we come and where the computation can be
+              done. In other words, we want either the left or the
+              right derivative and we want to completely ignore the
+              other side of the fence.
+            </p>
+
+            <p>
+              This case is especially important in constrained
+              optimization problems. For such problems, it is proven
+              that the optimum is located either at a point where all
+              derivatives are null <em>or exactly at the boundary</em>.
+              In order to handle these cases which are quite common,
+              we need to be able to compute derivatives at branching
+              points and to be consistent with the side where
+              computation is feasible.
+            </p>
+          </dd>
+        </dl>
+      </subsection>
+    </section>
+
+  </body>
+</document>

Propchange: commons/sandbox/nabla/trunk/src/site/xdoc/singularities.xml
------------------------------------------------------------------------------
    svn:eol-style = native



Mime
View raw message