001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.math4.analysis.differentiation;
018
019import java.io.Serializable;
020import java.util.Collections;
021import java.util.HashMap;
022import java.util.Map;
023
024import org.apache.commons.numbers.arrays.LinearCombination;
025import org.apache.commons.numbers.core.Precision;
026import org.apache.commons.math4.Field;
027import org.apache.commons.math4.FieldElement;
028import org.apache.commons.math4.RealFieldElement;
029import org.apache.commons.math4.exception.DimensionMismatchException;
030import org.apache.commons.math4.util.FastMath;
031import org.apache.commons.math4.util.MathUtils;
032
033/**
034 * First derivative computation with large number of variables.
035 * <p>
036 * This class plays a similar role to {@link DerivativeStructure}, with
037 * a focus on efficiency when dealing with large number of independent variables
038 * and most computation depend only on a few of them, and when only first derivative
039 * is desired. When these conditions are met, this class should be much faster than
040 * {@link DerivativeStructure} and use less memory.
041 * </p>
042 *
043 * @since 3.3
044 */
045public class SparseGradient implements RealFieldElement<SparseGradient>, Serializable {
046
047    /** Serializable UID. */
048    private static final long serialVersionUID = 20131025L;
049
050    /** Value of the calculation. */
051    private double value;
052
053    /** Stored derivative, each key representing a different independent variable. */
054    private final Map<Integer, Double> derivatives;
055
056    /** Internal constructor.
057     * @param value value of the function
058     * @param derivatives derivatives map, a deep copy will be performed,
059     * so the map given here will remain safe from changes in the new instance,
060     * may be null to create an empty derivatives map, i.e. a constant value
061     */
062    private SparseGradient(final double value, final Map<Integer, Double> derivatives) {
063        this.value = value;
064        this.derivatives = new HashMap<>();
065        if (derivatives != null) {
066            this.derivatives.putAll(derivatives);
067        }
068    }
069
070    /** Internal constructor.
071     * @param value value of the function
072     * @param scale scaling factor to apply to all derivatives
073     * @param derivatives derivatives map, a deep copy will be performed,
074     * so the map given here will remain safe from changes in the new instance,
075     * may be null to create an empty derivatives map, i.e. a constant value
076     */
077    private SparseGradient(final double value, final double scale,
078                             final Map<Integer, Double> derivatives) {
079        this.value = value;
080        this.derivatives = new HashMap<>();
081        if (derivatives != null) {
082            for (final Map.Entry<Integer, Double> entry : derivatives.entrySet()) {
083                this.derivatives.put(entry.getKey(), scale * entry.getValue());
084            }
085        }
086    }
087
088    /** Factory method creating a constant.
089     * @param value value of the constant
090     * @return a new instance
091     */
092    public static SparseGradient createConstant(final double value) {
093        return new SparseGradient(value, Collections.<Integer, Double> emptyMap());
094    }
095
096    /** Factory method creating an independent variable.
097     * @param idx index of the variable
098     * @param value value of the variable
099     * @return a new instance
100     */
101    public static SparseGradient createVariable(final int idx, final double value) {
102        return new SparseGradient(value, Collections.singletonMap(idx, 1.0));
103    }
104
105    /**
106     * Find the number of variables.
107     * @return number of variables
108     */
109    public int numVars() {
110        return derivatives.size();
111    }
112
113    /**
114     * Get the derivative with respect to a particular index variable.
115     *
116     * @param index index to differentiate with.
117     * @return derivative with respect to a particular index variable
118     */
119    public double getDerivative(final int index) {
120        final Double out = derivatives.get(index);
121        return (out == null) ? 0.0 : out;
122    }
123
124    /**
125     * Get the value of the function.
126     * @return value of the function.
127     */
128    public double getValue() {
129        return value;
130    }
131
132    /** {@inheritDoc} */
133    @Override
134    public double getReal() {
135        return value;
136    }
137
138    /** {@inheritDoc} */
139    @Override
140    public SparseGradient add(final SparseGradient a) {
141        final SparseGradient out = new SparseGradient(value + a.value, derivatives);
142        for (Map.Entry<Integer, Double> entry : a.derivatives.entrySet()) {
143            final int id = entry.getKey();
144            final Double old = out.derivatives.get(id);
145            if (old == null) {
146                out.derivatives.put(id, entry.getValue());
147            } else {
148                out.derivatives.put(id, old + entry.getValue());
149            }
150        }
151
152        return out;
153    }
154
155    /**
156     * Add in place.
157     * <p>
158     * This method is designed to be faster when used multiple times in a loop.
159     * </p>
160     * <p>
161     * The instance is changed here, in order to not change the
162     * instance the {@link #add(SparseGradient)} method should
163     * be used.
164     * </p>
165     * @param a instance to add
166     */
167    public void addInPlace(final SparseGradient a) {
168        value += a.value;
169        for (final Map.Entry<Integer, Double> entry : a.derivatives.entrySet()) {
170            final int id = entry.getKey();
171            final Double old = derivatives.get(id);
172            if (old == null) {
173                derivatives.put(id, entry.getValue());
174            } else {
175                derivatives.put(id, old + entry.getValue());
176            }
177        }
178    }
179
180    /** {@inheritDoc} */
181    @Override
182    public SparseGradient add(final double c) {
183        final SparseGradient out = new SparseGradient(value + c, derivatives);
184        return out;
185    }
186
187    /** {@inheritDoc} */
188    @Override
189    public SparseGradient subtract(final SparseGradient a) {
190        final SparseGradient out = new SparseGradient(value - a.value, derivatives);
191        for (Map.Entry<Integer, Double> entry : a.derivatives.entrySet()) {
192            final int id = entry.getKey();
193            final Double old = out.derivatives.get(id);
194            if (old == null) {
195                out.derivatives.put(id, -entry.getValue());
196            } else {
197                out.derivatives.put(id, old - entry.getValue());
198            }
199        }
200        return out;
201    }
202
203    /** {@inheritDoc} */
204    @Override
205    public SparseGradient subtract(double c) {
206        return new SparseGradient(value - c, derivatives);
207    }
208
209    /** {@inheritDoc} */
210    @Override
211    public SparseGradient multiply(final SparseGradient a) {
212        final SparseGradient out =
213            new SparseGradient(value * a.value, Collections.<Integer, Double> emptyMap());
214
215        // Derivatives.
216        for (Map.Entry<Integer, Double> entry : derivatives.entrySet()) {
217            out.derivatives.put(entry.getKey(), a.value * entry.getValue());
218        }
219        for (Map.Entry<Integer, Double> entry : a.derivatives.entrySet()) {
220            final int id = entry.getKey();
221            final Double old = out.derivatives.get(id);
222            if (old == null) {
223                out.derivatives.put(id, value * entry.getValue());
224            } else {
225                out.derivatives.put(id, old + value * entry.getValue());
226            }
227        }
228        return out;
229    }
230
231    /**
232     * Multiply in place.
233     * <p>
234     * This method is designed to be faster when used multiple times in a loop.
235     * </p>
236     * <p>
237     * The instance is changed here, in order to not change the
238     * instance the {@link #add(SparseGradient)} method should
239     * be used.
240     * </p>
241     * @param a instance to multiply
242     */
243    public void multiplyInPlace(final SparseGradient a) {
244        // Derivatives.
245        for (Map.Entry<Integer, Double> entry : derivatives.entrySet()) {
246            derivatives.put(entry.getKey(), a.value * entry.getValue());
247        }
248        for (Map.Entry<Integer, Double> entry : a.derivatives.entrySet()) {
249            final int id = entry.getKey();
250            final Double old = derivatives.get(id);
251            if (old == null) {
252                derivatives.put(id, value * entry.getValue());
253            } else {
254                derivatives.put(id, old + value * entry.getValue());
255            }
256        }
257        value *= a.value;
258    }
259
260    /** {@inheritDoc} */
261    @Override
262    public SparseGradient multiply(final double c) {
263        return new SparseGradient(value * c, c, derivatives);
264    }
265
266    /** {@inheritDoc} */
267    @Override
268    public SparseGradient multiply(final int n) {
269        return new SparseGradient(value * n, n, derivatives);
270    }
271
272    /** {@inheritDoc} */
273    @Override
274    public SparseGradient divide(final SparseGradient a) {
275        final SparseGradient out = new SparseGradient(value / a.value, Collections.<Integer, Double> emptyMap());
276
277        // Derivatives.
278        for (Map.Entry<Integer, Double> entry : derivatives.entrySet()) {
279            out.derivatives.put(entry.getKey(), entry.getValue() / a.value);
280        }
281        for (Map.Entry<Integer, Double> entry : a.derivatives.entrySet()) {
282            final int id = entry.getKey();
283            final Double old = out.derivatives.get(id);
284            if (old == null) {
285                out.derivatives.put(id, -out.value / a.value * entry.getValue());
286            } else {
287                out.derivatives.put(id, old - out.value / a.value * entry.getValue());
288            }
289        }
290        return out;
291    }
292
293    /** {@inheritDoc} */
294    @Override
295    public SparseGradient divide(final double c) {
296        return new SparseGradient(value / c, 1.0 / c, derivatives);
297    }
298
299    /** {@inheritDoc} */
300    @Override
301    public SparseGradient negate() {
302        return new SparseGradient(-value, -1.0, derivatives);
303    }
304
305    /** {@inheritDoc} */
306    @Override
307    public Field<SparseGradient> getField() {
308        return new Field<SparseGradient>() {
309
310            /** {@inheritDoc} */
311            @Override
312            public SparseGradient getZero() {
313                return createConstant(0);
314            }
315
316            /** {@inheritDoc} */
317            @Override
318            public SparseGradient getOne() {
319                return createConstant(1);
320            }
321
322            /** {@inheritDoc} */
323            @Override
324            public Class<? extends FieldElement<SparseGradient>> getRuntimeClass() {
325                return SparseGradient.class;
326            }
327
328        };
329    }
330
331    /** {@inheritDoc} */
332    @Override
333    public SparseGradient remainder(final double a) {
334        return new SparseGradient(FastMath.IEEEremainder(value, a), derivatives);
335    }
336
337    /** {@inheritDoc} */
338    @Override
339    public SparseGradient remainder(final SparseGradient a) {
340
341        // compute k such that lhs % rhs = lhs - k rhs
342        final double rem = FastMath.IEEEremainder(value, a.value);
343        final double k   = FastMath.rint((value - rem) / a.value);
344
345        return subtract(a.multiply(k));
346
347    }
348
349    /** {@inheritDoc} */
350    @Override
351    public SparseGradient abs() {
352        if (Double.doubleToLongBits(value) < 0) {
353            // we use the bits representation to also handle -0.0
354            return negate();
355        } else {
356            return this;
357        }
358    }
359
360    /** {@inheritDoc} */
361    @Override
362    public SparseGradient ceil() {
363        return createConstant(FastMath.ceil(value));
364    }
365
366    /** {@inheritDoc} */
367    @Override
368    public SparseGradient floor() {
369        return createConstant(FastMath.floor(value));
370    }
371
372    /** {@inheritDoc} */
373    @Override
374    public SparseGradient rint() {
375        return createConstant(FastMath.rint(value));
376    }
377
378    /** {@inheritDoc} */
379    @Override
380    public long round() {
381        return FastMath.round(value);
382    }
383
384    /** {@inheritDoc} */
385    @Override
386    public SparseGradient signum() {
387        return createConstant(FastMath.signum(value));
388    }
389
390    /** {@inheritDoc} */
391    @Override
392    public SparseGradient copySign(final SparseGradient sign) {
393        final long m = Double.doubleToLongBits(value);
394        final long s = Double.doubleToLongBits(sign.value);
395        if ((m >= 0 && s >= 0) || (m < 0 && s < 0)) { // Sign is currently OK
396            return this;
397        }
398        return negate(); // flip sign
399    }
400
401    /** {@inheritDoc} */
402    @Override
403    public SparseGradient copySign(final double sign) {
404        final long m = Double.doubleToLongBits(value);
405        final long s = Double.doubleToLongBits(sign);
406        if ((m >= 0 && s >= 0) || (m < 0 && s < 0)) { // Sign is currently OK
407            return this;
408        }
409        return negate(); // flip sign
410    }
411
412    /** {@inheritDoc} */
413    @Override
414    public SparseGradient scalb(final int n) {
415        final SparseGradient out = new SparseGradient(FastMath.scalb(value, n), Collections.<Integer, Double> emptyMap());
416        for (Map.Entry<Integer, Double> entry : derivatives.entrySet()) {
417            out.derivatives.put(entry.getKey(), FastMath.scalb(entry.getValue(), n));
418        }
419        return out;
420    }
421
422    /** {@inheritDoc} */
423    @Override
424    public SparseGradient hypot(final SparseGradient y) {
425        if (Double.isInfinite(value) || Double.isInfinite(y.value)) {
426            return createConstant(Double.POSITIVE_INFINITY);
427        } else if (Double.isNaN(value) || Double.isNaN(y.value)) {
428            return createConstant(Double.NaN);
429        } else {
430
431            final int expX = FastMath.getExponent(value);
432            final int expY = FastMath.getExponent(y.value);
433            if (expX > expY + 27) {
434                // y is negligible with respect to x
435                return abs();
436            } else if (expY > expX + 27) {
437                // x is negligible with respect to y
438                return y.abs();
439            } else {
440
441                // find an intermediate scale to avoid both overflow and underflow
442                final int middleExp = (expX + expY) / 2;
443
444                // scale parameters without losing precision
445                final SparseGradient scaledX = scalb(-middleExp);
446                final SparseGradient scaledY = y.scalb(-middleExp);
447
448                // compute scaled hypotenuse
449                final SparseGradient scaledH =
450                        scaledX.multiply(scaledX).add(scaledY.multiply(scaledY)).sqrt();
451
452                // remove scaling
453                return scaledH.scalb(middleExp);
454
455            }
456
457        }
458    }
459
460    /**
461     * Returns the hypotenuse of a triangle with sides {@code x} and {@code y}
462     * - sqrt(<i>x</i><sup>2</sup>&nbsp;+<i>y</i><sup>2</sup>)
463     * avoiding intermediate overflow or underflow.
464     *
465     * <ul>
466     * <li> If either argument is infinite, then the result is positive infinity.</li>
467     * <li> else, if either argument is NaN then the result is NaN.</li>
468     * </ul>
469     *
470     * @param x a value
471     * @param y a value
472     * @return sqrt(<i>x</i><sup>2</sup>&nbsp;+<i>y</i><sup>2</sup>)
473     */
474    public static SparseGradient hypot(final SparseGradient x, final SparseGradient y) {
475        return x.hypot(y);
476    }
477
478    /** {@inheritDoc} */
479    @Override
480    public SparseGradient reciprocal() {
481        return new SparseGradient(1.0 / value, -1.0 / (value * value), derivatives);
482    }
483
484    /** {@inheritDoc} */
485    @Override
486    public SparseGradient sqrt() {
487        final double sqrt = FastMath.sqrt(value);
488        return new SparseGradient(sqrt, 0.5 / sqrt, derivatives);
489    }
490
491    /** {@inheritDoc} */
492    @Override
493    public SparseGradient cbrt() {
494        final double cbrt = FastMath.cbrt(value);
495        return new SparseGradient(cbrt, 1.0 / (3 * cbrt * cbrt), derivatives);
496    }
497
498    /** {@inheritDoc} */
499    @Override
500    public SparseGradient rootN(final int n) {
501        if (n == 2) {
502            return sqrt();
503        } else if (n == 3) {
504            return cbrt();
505        } else {
506            final double root = FastMath.pow(value, 1.0 / n);
507            return new SparseGradient(root, 1.0 / (n * FastMath.pow(root, n - 1)), derivatives);
508        }
509    }
510
511    /** {@inheritDoc} */
512    @Override
513    public SparseGradient pow(final double p) {
514        return new SparseGradient(FastMath.pow(value,  p), p * FastMath.pow(value,  p - 1), derivatives);
515    }
516
517    /** {@inheritDoc} */
518    @Override
519    public SparseGradient pow(final int n) {
520        if (n == 0) {
521            return getField().getOne();
522        } else {
523            final double valueNm1 = FastMath.pow(value,  n - 1);
524            return new SparseGradient(value * valueNm1, n * valueNm1, derivatives);
525        }
526    }
527
528    /** {@inheritDoc} */
529    @Override
530    public SparseGradient pow(final SparseGradient e) {
531        return log().multiply(e).exp();
532    }
533
534    /** Compute a<sup>x</sup> where a is a double and x a {@link SparseGradient}
535     * @param a number to exponentiate
536     * @param x power to apply
537     * @return a<sup>x</sup>
538     */
539    public static SparseGradient pow(final double a, final SparseGradient x) {
540        if (a == 0) {
541            if (x.value == 0) {
542                return x.compose(1.0, Double.NEGATIVE_INFINITY);
543            } else if (x.value < 0) {
544                return x.compose(Double.NaN, Double.NaN);
545            } else {
546                return x.getField().getZero();
547            }
548        } else {
549            final double ax = FastMath.pow(a, x.value);
550            return new SparseGradient(ax, ax * FastMath.log(a), x.derivatives);
551        }
552    }
553
554    /** {@inheritDoc} */
555    @Override
556    public SparseGradient exp() {
557        final double e = FastMath.exp(value);
558        return new SparseGradient(e, e, derivatives);
559    }
560
561    /** {@inheritDoc} */
562    @Override
563    public SparseGradient expm1() {
564        return new SparseGradient(FastMath.expm1(value), FastMath.exp(value), derivatives);
565    }
566
567    /** {@inheritDoc} */
568    @Override
569    public SparseGradient log() {
570        return new SparseGradient(FastMath.log(value), 1.0 / value, derivatives);
571    }
572
573    /** Base 10 logarithm.
574     * @return base 10 logarithm of the instance
575     */
576    @Override
577    public SparseGradient log10() {
578        return new SparseGradient(FastMath.log10(value), 1.0 / (FastMath.log(10.0) * value), derivatives);
579    }
580
581    /** {@inheritDoc} */
582    @Override
583    public SparseGradient log1p() {
584        return new SparseGradient(FastMath.log1p(value), 1.0 / (1.0 + value), derivatives);
585    }
586
587    /** {@inheritDoc} */
588    @Override
589    public SparseGradient cos() {
590        return new SparseGradient(FastMath.cos(value), -FastMath.sin(value), derivatives);
591    }
592
593    /** {@inheritDoc} */
594    @Override
595    public SparseGradient sin() {
596        return new SparseGradient(FastMath.sin(value), FastMath.cos(value), derivatives);
597    }
598
599    /** {@inheritDoc} */
600    @Override
601    public SparseGradient tan() {
602        final double t = FastMath.tan(value);
603        return new SparseGradient(t, 1 + t * t, derivatives);
604    }
605
606    /** {@inheritDoc} */
607    @Override
608    public SparseGradient acos() {
609        return new SparseGradient(FastMath.acos(value), -1.0 / FastMath.sqrt(1 - value * value), derivatives);
610    }
611
612    /** {@inheritDoc} */
613    @Override
614    public SparseGradient asin() {
615        return new SparseGradient(FastMath.asin(value), 1.0 / FastMath.sqrt(1 - value * value), derivatives);
616    }
617
618    /** {@inheritDoc} */
619    @Override
620    public SparseGradient atan() {
621        return new SparseGradient(FastMath.atan(value), 1.0 / (1 + value * value), derivatives);
622    }
623
624    /** {@inheritDoc} */
625    @Override
626    public SparseGradient atan2(final SparseGradient x) {
627
628        // compute r = sqrt(x^2+y^2)
629        final SparseGradient r = multiply(this).add(x.multiply(x)).sqrt();
630
631        final SparseGradient a;
632        if (x.value >= 0) {
633
634            // compute atan2(y, x) = 2 atan(y / (r + x))
635            a = divide(r.add(x)).atan().multiply(2);
636
637        } else {
638
639            // compute atan2(y, x) = +/- pi - 2 atan(y / (r - x))
640            final SparseGradient tmp = divide(r.subtract(x)).atan().multiply(-2);
641            a = tmp.add(tmp.value <= 0 ? -FastMath.PI : FastMath.PI);
642
643        }
644
645        // fix value to take special cases (+0/+0, +0/-0, -0/+0, -0/-0, +/-infinity) correctly
646        a.value = FastMath.atan2(value, x.value);
647
648        return a;
649
650    }
651
652    /** Two arguments arc tangent operation.
653     * @param y first argument of the arc tangent
654     * @param x second argument of the arc tangent
655     * @return atan2(y, x)
656     */
657    public static SparseGradient atan2(final SparseGradient y, final SparseGradient x) {
658        return y.atan2(x);
659    }
660
661    /** {@inheritDoc} */
662    @Override
663    public SparseGradient cosh() {
664        return new SparseGradient(FastMath.cosh(value), FastMath.sinh(value), derivatives);
665    }
666
667    /** {@inheritDoc} */
668    @Override
669    public SparseGradient sinh() {
670        return new SparseGradient(FastMath.sinh(value), FastMath.cosh(value), derivatives);
671    }
672
673    /** {@inheritDoc} */
674    @Override
675    public SparseGradient tanh() {
676        final double t = FastMath.tanh(value);
677        return new SparseGradient(t, 1 - t * t, derivatives);
678    }
679
680    /** {@inheritDoc} */
681    @Override
682    public SparseGradient acosh() {
683        return new SparseGradient(FastMath.acosh(value), 1.0 / FastMath.sqrt(value * value - 1.0), derivatives);
684    }
685
686    /** {@inheritDoc} */
687    @Override
688    public SparseGradient asinh() {
689        return new SparseGradient(FastMath.asinh(value), 1.0 / FastMath.sqrt(value * value + 1.0), derivatives);
690    }
691
692    /** {@inheritDoc} */
693    @Override
694    public SparseGradient atanh() {
695        return new SparseGradient(FastMath.atanh(value), 1.0 / (1.0 - value * value), derivatives);
696    }
697
698    /** Convert radians to degrees, with error of less than 0.5 ULP
699     *  @return instance converted into degrees
700     */
701    public SparseGradient toDegrees() {
702        return new SparseGradient(FastMath.toDegrees(value), FastMath.toDegrees(1.0), derivatives);
703    }
704
705    /** Convert degrees to radians, with error of less than 0.5 ULP
706     *  @return instance converted into radians
707     */
708    public SparseGradient toRadians() {
709        return new SparseGradient(FastMath.toRadians(value), FastMath.toRadians(1.0), derivatives);
710    }
711
712    /** Evaluate Taylor expansion of a sparse gradient.
713     * @param delta parameters offsets (&Delta;x, &Delta;y, ...)
714     * @return value of the Taylor expansion at x + &Delta;x, y + &Delta;y, ...
715     */
716    public double taylor(final double ... delta) {
717        double y = value;
718        for (int i = 0; i < delta.length; ++i) {
719            y += delta[i] * getDerivative(i);
720        }
721        return y;
722    }
723
724    /** Compute composition of the instance by a univariate function.
725     * @param f0 value of the function at (i.e. f({@link #getValue()}))
726     * @param f1 first derivative of the function at
727     * the current point (i.e. f'({@link #getValue()}))
728     * @return f(this)
729    */
730    public SparseGradient compose(final double f0, final double f1) {
731        return new SparseGradient(f0, f1, derivatives);
732    }
733
734    /** {@inheritDoc} */
735    @Override
736    public SparseGradient linearCombination(final SparseGradient[] a,
737                                              final SparseGradient[] b)
738        throws DimensionMismatchException {
739
740        // compute a simple value, with all partial derivatives
741        SparseGradient out = a[0].getField().getZero();
742        for (int i = 0; i < a.length; ++i) {
743            out = out.add(a[i].multiply(b[i]));
744        }
745
746        // recompute an accurate value, taking care of cancellations
747        final double[] aDouble = new double[a.length];
748        for (int i = 0; i < a.length; ++i) {
749            aDouble[i] = a[i].getValue();
750        }
751        final double[] bDouble = new double[b.length];
752        for (int i = 0; i < b.length; ++i) {
753            bDouble[i] = b[i].getValue();
754        }
755        out.value = LinearCombination.value(aDouble, bDouble);
756
757        return out;
758
759    }
760
761    /** {@inheritDoc} */
762    @Override
763    public SparseGradient linearCombination(final double[] a, final SparseGradient[] b) {
764
765        // compute a simple value, with all partial derivatives
766        SparseGradient out = b[0].getField().getZero();
767        for (int i = 0; i < a.length; ++i) {
768            out = out.add(b[i].multiply(a[i]));
769        }
770
771        // recompute an accurate value, taking care of cancellations
772        final double[] bDouble = new double[b.length];
773        for (int i = 0; i < b.length; ++i) {
774            bDouble[i] = b[i].getValue();
775        }
776        out.value = LinearCombination.value(a, bDouble);
777
778        return out;
779
780    }
781
782    /** {@inheritDoc} */
783    @Override
784    public SparseGradient linearCombination(final SparseGradient a1, final SparseGradient b1,
785                                              final SparseGradient a2, final SparseGradient b2) {
786
787        // compute a simple value, with all partial derivatives
788        SparseGradient out = a1.multiply(b1).add(a2.multiply(b2));
789
790        // recompute an accurate value, taking care of cancellations
791        out.value = LinearCombination.value(a1.value, b1.value, a2.value, b2.value);
792
793        return out;
794
795    }
796
797    /** {@inheritDoc} */
798    @Override
799    public SparseGradient linearCombination(final double a1, final SparseGradient b1,
800                                              final double a2, final SparseGradient b2) {
801
802        // compute a simple value, with all partial derivatives
803        SparseGradient out = b1.multiply(a1).add(b2.multiply(a2));
804
805        // recompute an accurate value, taking care of cancellations
806        out.value = LinearCombination.value(a1, b1.value, a2, b2.value);
807
808        return out;
809
810    }
811
812    /** {@inheritDoc} */
813    @Override
814    public SparseGradient linearCombination(final SparseGradient a1, final SparseGradient b1,
815                                              final SparseGradient a2, final SparseGradient b2,
816                                              final SparseGradient a3, final SparseGradient b3) {
817
818        // compute a simple value, with all partial derivatives
819        SparseGradient out = a1.multiply(b1).add(a2.multiply(b2)).add(a3.multiply(b3));
820
821        // recompute an accurate value, taking care of cancellations
822        out.value = LinearCombination.value(a1.value, b1.value,
823                                                 a2.value, b2.value,
824                                                 a3.value, b3.value);
825
826        return out;
827
828    }
829
830    /** {@inheritDoc} */
831    @Override
832    public SparseGradient linearCombination(final double a1, final SparseGradient b1,
833                                              final double a2, final SparseGradient b2,
834                                              final double a3, final SparseGradient b3) {
835
836        // compute a simple value, with all partial derivatives
837        SparseGradient out = b1.multiply(a1).add(b2.multiply(a2)).add(b3.multiply(a3));
838
839        // recompute an accurate value, taking care of cancellations
840        out.value = LinearCombination.value(a1, b1.value,
841                                                 a2, b2.value,
842                                                 a3, b3.value);
843
844        return out;
845
846    }
847
848    /** {@inheritDoc} */
849    @Override
850    public SparseGradient linearCombination(final SparseGradient a1, final SparseGradient b1,
851                                              final SparseGradient a2, final SparseGradient b2,
852                                              final SparseGradient a3, final SparseGradient b3,
853                                              final SparseGradient a4, final SparseGradient b4) {
854
855        // compute a simple value, with all partial derivatives
856        SparseGradient out = a1.multiply(b1).add(a2.multiply(b2)).add(a3.multiply(b3)).add(a4.multiply(b4));
857
858        // recompute an accurate value, taking care of cancellations
859        out.value = LinearCombination.value(a1.value, b1.value,
860                                                 a2.value, b2.value,
861                                                 a3.value, b3.value,
862                                                 a4.value, b4.value);
863
864        return out;
865
866    }
867
868    /** {@inheritDoc} */
869    @Override
870    public SparseGradient linearCombination(final double a1, final SparseGradient b1,
871                                              final double a2, final SparseGradient b2,
872                                              final double a3, final SparseGradient b3,
873                                              final double a4, final SparseGradient b4) {
874
875        // compute a simple value, with all partial derivatives
876        SparseGradient out = b1.multiply(a1).add(b2.multiply(a2)).add(b3.multiply(a3)).add(b4.multiply(a4));
877
878        // recompute an accurate value, taking care of cancellations
879        out.value = LinearCombination.value(a1, b1.value,
880                                                 a2, b2.value,
881                                                 a3, b3.value,
882                                                 a4, b4.value);
883
884        return out;
885
886    }
887
888    /**
889     * Test for the equality of two sparse gradients.
890     * <p>
891     * Sparse gradients are considered equal if they have the same value
892     * and the same derivatives.
893     * </p>
894     * @param other Object to test for equality to this
895     * @return true if two sparse gradients are equal
896     */
897    @Override
898    public boolean equals(Object other) {
899
900        if (this == other) {
901            return true;
902        }
903
904        if (other instanceof SparseGradient) {
905            final SparseGradient rhs = (SparseGradient)other;
906            if (!Precision.equals(value, rhs.value, 1)) {
907                return false;
908            }
909            if (derivatives.size() != rhs.derivatives.size()) {
910                return false;
911            }
912            for (final Map.Entry<Integer, Double> entry : derivatives.entrySet()) {
913                if (!rhs.derivatives.containsKey(entry.getKey())) {
914                    return false;
915                }
916                if (!Precision.equals(entry.getValue(), rhs.derivatives.get(entry.getKey()), 1)) {
917                    return false;
918                }
919            }
920            return true;
921        }
922
923        return false;
924
925    }
926
927    /**
928     * Get a hashCode for the derivative structure.
929     * @return a hash code value for this object
930     * @since 3.2
931     */
932    @Override
933    public int hashCode() {
934        return 743 + 809 * MathUtils.hash(value) + 167 * derivatives.hashCode();
935    }
936
937}