1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 package org.hipparchus.analysis.polynomials;
23
24 import java.util.ArrayList;
25 import java.util.HashMap;
26 import java.util.List;
27 import java.util.Map;
28
29 import org.hipparchus.fraction.BigFraction;
30 import org.hipparchus.util.CombinatoricsUtils;
31 import org.hipparchus.util.FastMath;
32
33
34
35
36
37 public class PolynomialsUtils {
38
39
40 private static final List<BigFraction> CHEBYSHEV_COEFFICIENTS;
41
42
43 private static final List<BigFraction> HERMITE_COEFFICIENTS;
44
45
46 private static final List<BigFraction> LAGUERRE_COEFFICIENTS;
47
48
49 private static final List<BigFraction> LEGENDRE_COEFFICIENTS;
50
51
52 private static final Map<JacobiKey, List<BigFraction>> JACOBI_COEFFICIENTS;
53
54 static {
55
56
57
58 CHEBYSHEV_COEFFICIENTS = new ArrayList<>();
59 CHEBYSHEV_COEFFICIENTS.add(BigFraction.ONE);
60 CHEBYSHEV_COEFFICIENTS.add(BigFraction.ZERO);
61 CHEBYSHEV_COEFFICIENTS.add(BigFraction.ONE);
62
63
64
65 HERMITE_COEFFICIENTS = new ArrayList<>();
66 HERMITE_COEFFICIENTS.add(BigFraction.ONE);
67 HERMITE_COEFFICIENTS.add(BigFraction.ZERO);
68 HERMITE_COEFFICIENTS.add(BigFraction.TWO);
69
70
71
72 LAGUERRE_COEFFICIENTS = new ArrayList<>();
73 LAGUERRE_COEFFICIENTS.add(BigFraction.ONE);
74 LAGUERRE_COEFFICIENTS.add(BigFraction.ONE);
75 LAGUERRE_COEFFICIENTS.add(BigFraction.MINUS_ONE);
76
77
78
79 LEGENDRE_COEFFICIENTS = new ArrayList<>();
80 LEGENDRE_COEFFICIENTS.add(BigFraction.ONE);
81 LEGENDRE_COEFFICIENTS.add(BigFraction.ZERO);
82 LEGENDRE_COEFFICIENTS.add(BigFraction.ONE);
83
84
85 JACOBI_COEFFICIENTS = new HashMap<>();
86
87 }
88
89
90
91
92 private PolynomialsUtils() {
93 }
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109 public static PolynomialFunction createChebyshevPolynomial(final int degree) {
110 return buildPolynomial(degree, CHEBYSHEV_COEFFICIENTS,
111 new RecurrenceCoefficientsGenerator() {
112
113 private final BigFraction[] coeffs = { BigFraction.ZERO, BigFraction.TWO, BigFraction.ONE };
114
115 @Override
116 public BigFraction[] generate(int k) {
117 return coeffs;
118 }
119 });
120 }
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137 public static PolynomialFunction createHermitePolynomial(final int degree) {
138 return buildPolynomial(degree, HERMITE_COEFFICIENTS,
139 new RecurrenceCoefficientsGenerator() {
140
141 @Override
142 public BigFraction[] generate(int k) {
143 return new BigFraction[] {
144 BigFraction.ZERO,
145 BigFraction.TWO,
146 new BigFraction(2 * k)};
147 }
148 });
149 }
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165 public static PolynomialFunction createLaguerrePolynomial(final int degree) {
166 return buildPolynomial(degree, LAGUERRE_COEFFICIENTS,
167 new RecurrenceCoefficientsGenerator() {
168
169 @Override
170 public BigFraction[] generate(int k) {
171 final int kP1 = k + 1;
172 return new BigFraction[] {
173 new BigFraction(2 * k + 1, kP1),
174 new BigFraction(-1, kP1),
175 new BigFraction(k, kP1)};
176 }
177 });
178 }
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194 public static PolynomialFunction createLegendrePolynomial(final int degree) {
195 return buildPolynomial(degree, LEGENDRE_COEFFICIENTS,
196 new RecurrenceCoefficientsGenerator() {
197
198 @Override
199 public BigFraction[] generate(int k) {
200 final int kP1 = k + 1;
201 return new BigFraction[] {
202 BigFraction.ZERO,
203 new BigFraction(k + kP1, kP1),
204 new BigFraction(k, kP1)};
205 }
206 });
207 }
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227 public static PolynomialFunction createJacobiPolynomial(final int degree, final int v, final int w) {
228
229
230 final JacobiKey key = new JacobiKey(v, w);
231
232 if (!JACOBI_COEFFICIENTS.containsKey(key)) {
233
234
235 final List<BigFraction> list = new ArrayList<>();
236 JACOBI_COEFFICIENTS.put(key, list);
237
238
239 list.add(BigFraction.ONE);
240
241
242 list.add(new BigFraction(v - w, 2));
243 list.add(new BigFraction(2 + v + w, 2));
244
245 }
246
247 return buildPolynomial(degree, JACOBI_COEFFICIENTS.get(key),
248 new RecurrenceCoefficientsGenerator() {
249
250 @Override
251 public BigFraction[] generate(int k) {
252 k++;
253 final int kvw = k + v + w;
254 final int twoKvw = kvw + k;
255 final int twoKvwM1 = twoKvw - 1;
256 final int twoKvwM2 = twoKvw - 2;
257 final int den = 2 * k * kvw * twoKvwM2;
258
259 return new BigFraction[] {
260 new BigFraction(twoKvwM1 * (v * v - w * w), den),
261 new BigFraction(twoKvwM1 * twoKvw * twoKvwM2, den),
262 new BigFraction(2 * (k + v - 1) * (k + w - 1) * twoKvw, den)
263 };
264 }
265 });
266
267 }
268
269
270 private static class JacobiKey {
271
272
273 private final int v;
274
275
276 private final int w;
277
278
279
280
281
282 JacobiKey(final int v, final int w) {
283 this.v = v;
284 this.w = w;
285 }
286
287
288
289
290 @Override
291 public int hashCode() {
292 return (v << 16) ^ w;
293 }
294
295
296
297
298
299 @Override
300 public boolean equals(final Object key) {
301
302 if ((key == null) || !(key instanceof JacobiKey)) {
303 return false;
304 }
305
306 final JacobiKey otherK = (JacobiKey) key;
307 return (v == otherK.v) && (w == otherK.w);
308
309 }
310 }
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329 public static double[] shift(final double[] coefficients,
330 final double shift) {
331 final int dp1 = coefficients.length;
332 final double[] newCoefficients = new double[dp1];
333
334
335 final int[][] coeff = new int[dp1][dp1];
336 for (int i = 0; i < dp1; i++){
337 for(int j = 0; j <= i; j++){
338 coeff[i][j] = (int) CombinatoricsUtils.binomialCoefficient(i, j);
339 }
340 }
341
342
343 for (int i = 0; i < dp1; i++){
344 newCoefficients[0] += coefficients[i] * FastMath.pow(shift, i);
345 }
346
347
348 final int d = dp1 - 1;
349 for (int i = 0; i < d; i++) {
350 for (int j = i; j < d; j++){
351 newCoefficients[i + 1] += coeff[j + 1][j - i] *
352 coefficients[j + 1] * FastMath.pow(shift, j - i);
353 }
354 }
355
356 return newCoefficients;
357 }
358
359
360
361
362
363
364
365
366 private static PolynomialFunction buildPolynomial(final int degree,
367 final List<BigFraction> coefficients,
368 final RecurrenceCoefficientsGenerator generator) {
369
370 synchronized (coefficients) {
371 final int maxDegree = (int) FastMath.floor(FastMath.sqrt(2 * coefficients.size())) - 1;
372 if (degree > maxDegree) {
373 computeUpToDegree(degree, maxDegree, generator, coefficients);
374 }
375 }
376
377
378
379
380
381
382
383
384
385 final int start = degree * (degree + 1) / 2;
386
387 final double[] a = new double[degree + 1];
388 for (int i = 0; i <= degree; ++i) {
389 a[i] = coefficients.get(start + i).doubleValue();
390 }
391
392
393 return new PolynomialFunction(a);
394
395 }
396
397
398
399
400
401
402
403 private static void computeUpToDegree(final int degree, final int maxDegree,
404 final RecurrenceCoefficientsGenerator generator,
405 final List<BigFraction> coefficients) {
406
407 int startK = (maxDegree - 1) * maxDegree / 2;
408 for (int k = maxDegree; k < degree; ++k) {
409
410
411 int startKm1 = startK;
412 startK += k;
413
414
415 BigFraction[] ai = generator.generate(k);
416
417 BigFraction ck = coefficients.get(startK);
418 BigFraction ckm1 = coefficients.get(startKm1);
419
420
421 coefficients.add(ck.multiply(ai[0]).subtract(ckm1.multiply(ai[2])));
422
423
424 for (int i = 1; i < k; ++i) {
425 final BigFraction ckPrev = ck;
426 ck = coefficients.get(startK + i);
427 ckm1 = coefficients.get(startKm1 + i);
428 coefficients.add(ck.multiply(ai[0]).add(ckPrev.multiply(ai[1])).subtract(ckm1.multiply(ai[2])));
429 }
430
431
432 final BigFraction ckPrev = ck;
433 ck = coefficients.get(startK + k);
434 coefficients.add(ck.multiply(ai[0]).add(ckPrev.multiply(ai[1])));
435
436
437 coefficients.add(ck.multiply(ai[1]));
438
439 }
440
441 }
442
443
444 private interface RecurrenceCoefficientsGenerator {
445
446
447
448
449
450
451 BigFraction[] generate(int k);
452 }
453
454 }