KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > JSci > maths > polynomials > PolynomialMath


1 package JSci.maths.polynomials;
2
3 import JSci.maths.AbstractMath;
4 import JSci.maths.Complex;
5 import JSci.maths.matrices.AbstractComplexSquareMatrix;
6 import JSci.maths.matrices.AbstractDoubleSquareMatrix;
7 import JSci.maths.matrices.ComplexSquareMatrix;
8 import JSci.maths.matrices.DoubleSquareMatrix;
9
10 /**
11  *
12  * @author b.dietrich
13  */

14 public final class PolynomialMath extends AbstractMath {
15         private PolynomialMath() {}
16
17     /**
18      * Returns the companion matrix of a given polynomial.
19      * The eigenvalues of the companion matrix are the roots of the polynomial.
20      *
21      * @param p the polynomial
22      *
23      * @return the companion matrix
24      * @jsci.planetmath CompanionMatrix
25      */

26     public static AbstractDoubleSquareMatrix toCompanionMatrix( RealPolynomial p ) {
27         RealPolynomial np = normalize(p);
28
29         int n = np.degree();
30         if ( n < 1 ) {
31             throw new IllegalArgumentException JavaDoc( "Cannot get a companion matrix for a constant factor" );
32         }
33
34         AbstractDoubleSquareMatrix dsm = new DoubleSquareMatrix( n );
35
36         for ( int k = 0; k < (n-1); k++ ) {
37         // fill subdiagonal
38
dsm.setElement( k+1, k, 1.0 );
39         // fill lastCol
40
dsm.setElement( k, n-1, np.getCoefficientAsDouble( k ) );
41         }
42         // fill lastRow/lastCol
43
dsm.setElement( n-1, n-1, np.getCoefficientAsDouble( n-1 ) );
44
45         return dsm;
46     }
47     public static AbstractComplexSquareMatrix toCompanionMatrix( ComplexPolynomial p ) {
48         ComplexPolynomial np = normalize(p);
49
50         int n = np.degree();
51         if ( n < 1 ) {
52             throw new IllegalArgumentException JavaDoc( "Cannot get a companion matrix for a constant factor" );
53         }
54
55         AbstractComplexSquareMatrix csm = new ComplexSquareMatrix( n );
56
57         for ( int k = 0; k < ( n-1 ); k++ ) {
58         // fill subdiagonal
59
csm.setElement( k+1, k, 1.0, 0.0 );
60         // fill lastCol
61
csm.setElement( k, n-1, np.getCoefficientAsComplex( k ) );
62         }
63         // fill lastRow/lastCol
64
csm.setElement( n-1, n-1, np.getCoefficientAsComplex( n-1 ) );
65
66         return csm;
67     }
68
69     /**
70      * Calculates the roots of a given polynomial by solving the
71      * eigenvalue problem for the companion matrix.
72      * This is not yet implemented (depends on a QR- decomposition)
73      * @param p the polynomial
74      *
75      * @return (unordered) list of roots.
76      */

77     public static Complex[] findRoots( RealPolynomial p ) {
78         AbstractDoubleSquareMatrix matrix = toCompanionMatrix( p );
79
80         // return solveEigenvalueByQR(c);
81
throw new java.lang.UnsupportedOperationException JavaDoc("Not yet implemented.");
82     }
83
84     /**
85      * Get the maximum degree of two polynomials
86      * @param p1
87      * @param p2
88      */

89     public static int maxDegree( Polynomial p1, Polynomial p2 ) {
90         return Math.max( p1.degree(), p2.degree() );
91     }
92
93     /**
94      * Get the minimal degree of two polynomials
95      * @param p1
96      * @param p2
97      */

98     public static int minDegree( Polynomial p1, Polynomial p2 ) {
99         return Math.min( p1.degree(), p2.degree() );
100     }
101
102     /**
103      * Evaluates a polynomial by Horner's scheme.
104      * @param p
105      * @param t
106      */

107     public static double evalPolynomial( RealPolynomial p, double t ) {
108         final int n = p.degree();
109         double r = p.getCoefficientAsDouble(n);
110         for ( int i = n-1; i >= 0; i-- ) {
111             r = p.getCoefficientAsDouble(i) + ( r * t );
112         }
113
114         return r;
115     }
116
117     /**
118      * Evaluates a polynomial by Horner's scheme.
119      * @param p
120      * @param t
121      */

122     public static Complex evalPolynomial( ComplexPolynomial p, Complex t ) {
123         final int n = p.degree();
124         Complex r = p.getCoefficientAsComplex(n);
125         for ( int i = n-1; i >= 0; i-- ) {
126             r = p.getCoefficientAsComplex(i).add( r.multiply( t ) );
127         }
128
129         return r;
130     }
131
132     /**
133      * Interpolates a polynomial.
134      * Caveat: this method is brute-force, slow and not very stable.
135      * It shouldn't be used for more than approx. 10 points.
136      * Remember the strong variations of higher degree polynomials.
137      *
138      * @param samplingPoints an array[2][n] where array[0] denotes x-values, array[1] y-values
139      */

140     public static RealPolynomial interpolateLagrange( double[][] samplingPoints ) {
141         RealLagrangeBasis r = new RealLagrangeBasis( samplingPoints[0] );
142         return ( (RealPolynomial) r.superposition( samplingPoints[1] ) );
143     }
144
145     /**
146      * Interpolates a polynomial.
147      * Caveat: this method is brute-force, slow and not very stable.
148      * It shouldn't be used for more than approx. 10 points.
149      * Remember the strong variations of higher degree polynomials.
150      *
151      * @param samplingPoints an array[2][n] where array[0] denotes x-values, array[1] y-values
152      */

153     public static ComplexPolynomial interpolateLagrange( Complex[][] samplingPoints ) {
154         ComplexLagrangeBasis r = new ComplexLagrangeBasis( samplingPoints[0] );
155         return ( (ComplexPolynomial) r.superposition( samplingPoints[1] ) );
156     }
157
158     /**
159      * Normalizes a given real polynomial, i.e. divide by the leading coefficient.
160      * @param p
161      */

162     public static RealPolynomial normalize( RealPolynomial p ) {
163         final int n = p.degree();
164         final double c = p.getCoefficientAsDouble( n );
165         double[] m = new double[n+1];
166         m[n] = 1.0;
167         for ( int i = 0; i < n; i++ ) {
168             m[i] = p.getCoefficientAsDouble( i ) / c;
169         }
170
171         return new RealPolynomial( m );
172     }
173     /**
174      * Normalizes a given complex polynomial, i.e. divide by the leading coefficient.
175      * @param p
176      */

177     public static ComplexPolynomial normalize( ComplexPolynomial p ) {
178         final int n = p.degree();
179         final Complex c = p.getCoefficientAsComplex( n );
180         Complex[] m = new Complex[n+1];
181         m[n] = Complex.ONE;
182         for ( int i = 0; i < n; i++ ) {
183             m[i] = p.getCoefficientAsComplex( i ).divide( c );
184         }
185
186         return new ComplexPolynomial( m );
187     }
188
189     /**
190      *
191      * Try to cast a Polynomial to a complex polynomial
192      */

193     public static ComplexPolynomial toComplex( Polynomial p ) {
194         if ( p instanceof ComplexPolynomial ) {
195             return (ComplexPolynomial) p;
196         } else if ( p instanceof RealPolynomial ) {
197             double[] d = ( (RealPolynomial) p ).getCoefficientsAsDoubles();
198             Complex[] c = new Complex[d.length];
199             for ( int k = 0; k < d.length; k++ ) {
200                 c[k] = new Complex( d[k], 0 );
201             }
202
203             return new ComplexPolynomial( c );
204         } else {
205             throw new IllegalArgumentException JavaDoc("Polynomial class not recognised by this method.");
206         }
207     }
208 }
209
210
Popular Tags