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="/maillists.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="UTF8" ?>
+<!
+ 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/LICENSE2.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
+ subexpressions 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 subexpressions 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 < 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 < 0)</code> statement into
+ <code>if (t <= 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 < 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 < 0)</code> statement into <code>if (t <=
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:eolstyle = native
