My Project
Loading...
Searching...
No Matches
Public Member Functions | Private Member Functions | Private Attributes
vandermonde Class Reference

vandermonde system solver for interpolating polynomials from their values More...

#include <mpr_numeric.h>

Public Member Functions

 vandermonde (const long _cn, const long _n, const long _maxdeg, number *_p, const bool _homog=true)
 
 ~vandermonde ()
 
number * interpolateDense (const number *q)
 Solves the Vandermode linear system \sum_{i=1}^{n} x_i^k-1 w_i = q_k, k=1,..,n. More...
 
poly numvec2poly (const number *q)
 

Private Member Functions

void init ()
 

Private Attributes

long n
 
long cn
 
long maxdeg
 
long l
 
number * p
 
number * x
 
bool homog
 

Detailed Description

vandermonde system solver for interpolating polynomials from their values

Definition at line 28 of file mpr_numeric.h.

Constructor & Destructor Documentation

◆ vandermonde()

vandermonde::vandermonde ( const long  _cn,
const long  _n,
const long  _maxdeg,
number *  _p,
const bool  _homog = true 
)

Definition at line 35 of file mpr_numeric.cc.

37 : n(_n), cn(_cn), maxdeg(_maxdeg), p(_p), homog(_homog)
38{
39 long j;
40 l= (long)pow((double)maxdeg+1,(int)n);
41 x= (number *)omAlloc( cn * sizeof(number) );
42 for ( j= 0; j < cn; j++ ) x[j]= nInit(1);
43 init();
44}
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:411
void init()
Definition: mpr_numeric.cc:53
number * x
Definition: mpr_numeric.h:55
number * p
Definition: mpr_numeric.h:54
int j
Definition: facHensel.cc:110
#define nInit(i)
Definition: numbers.h:24
#define omAlloc(size)
Definition: omAllocDecl.h:210

◆ ~vandermonde()

vandermonde::~vandermonde ( )

Definition at line 46 of file mpr_numeric.cc.

47{
48 int j;
49 for ( j= 0; j < cn; j++ ) nDelete( x+j );
50 omFreeSize( (void *)x, cn * sizeof( number ) );
51}
#define nDelete(n)
Definition: numbers.h:16
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260

Member Function Documentation

◆ init()

void vandermonde::init ( )
private

Definition at line 53 of file mpr_numeric.cc.

54{
55 int j;
56 long i,c,sum;
57 number tmp,tmp1;
58
59 c=0;
60 sum=0;
61
62 intvec exp( n );
63 for ( j= 0; j < n; j++ ) exp[j]=0;
64
65 for ( i= 0; i < l; i++ )
66 {
67 if ( !homog || (sum == maxdeg) )
68 {
69 for ( j= 0; j < n; j++ )
70 {
71 nPower( p[j], exp[j], &tmp );
72 tmp1 = nMult( tmp, x[c] );
73 x[c]= tmp1;
74 nDelete( &tmp );
75 }
76 c++;
77 }
78 exp[0]++;
79 sum=0;
80 for ( j= 0; j < n - 1; j++ )
81 {
82 if ( exp[j] > maxdeg )
83 {
84 exp[j]= 0;
85 exp[j + 1]++;
86 }
87 sum+= exp[j];
88 }
89 sum+= exp[n - 1];
90 }
91}
int i
Definition: cfEzgcd.cc:132
Definition: intvec.h:23
CFList tmp1
Definition: facFqBivar.cc:72
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
#define nMult(n1, n2)
Definition: numbers.h:17
#define nPower(a, b, res)
Definition: numbers.h:38

◆ interpolateDense()

number * vandermonde::interpolateDense ( const number *  q)

Solves the Vandermode linear system \sum_{i=1}^{n} x_i^k-1 w_i = q_k, k=1,..,n.

Any computations are done using type number to get high pecision results.

Parameters
qn-tuple of results (right hand of equations)
Returns
w n-tuple of coefficients of resulting polynomial, lowest deg first

Definition at line 146 of file mpr_numeric.cc.

147{
148 int i,j,k;
149 number newnum,tmp1;
150 number b,t,xx,s;
151 number *c;
152 number *w;
153
154 b=t=xx=s=tmp1=NULL;
155
156 w= (number *)omAlloc( cn * sizeof(number) );
157 c= (number *)omAlloc( cn * sizeof(number) );
158 for ( j= 0; j < cn; j++ )
159 {
160 w[j]= nInit(0);
161 c[j]= nInit(0);
162 }
163
164 if ( cn == 1 )
165 {
166 nDelete( &w[0] );
167 w[0]= nCopy(q[0]);
168 }
169 else
170 {
171 nDelete( &c[cn-1] );
172 c[cn-1]= nCopy(x[0]);
173 c[cn-1]= nInpNeg(c[cn-1]); // c[cn]= -x[1]
174
175 for ( i= 1; i < cn; i++ ) { // i=2; i <= cn
176 if (xx!=NULL) nDelete( &xx );
177 xx= nCopy(x[i]);
178 xx= nInpNeg(xx); // xx= -x[i]
179
180 for ( j= (cn-i-1); j <= (cn-2); j++) { // j=(cn+1-i); j <= (cn-1)
181 if (tmp1!=NULL) nDelete( &tmp1 );
182 tmp1= nMult( xx, c[j+1] ); // c[j]= c[j] + (xx * c[j+1])
183 newnum= nAdd( c[j], tmp1 );
184 nDelete( &c[j] );
185 c[j]= newnum;
186 }
187
188 newnum= nAdd( xx, c[cn-1] ); // c[cn-1]= c[cn-1] + xx
189 nDelete( &c[cn-1] );
190 c[cn-1]= newnum;
191 }
192
193 for ( i= 0; i < cn; i++ ) { // i=1; i <= cn
194 nDelete( &xx );
195 xx= nCopy(x[i]); // xx= x[i]
196
197 if (t!=NULL) nDelete( &t );
198 t= nInit( 1 ); // t= b= 1
199 if (b!=NULL) nDelete( &b );
200 b= nInit( 1 );
201 if (s!=NULL) nDelete( &s ); // s= q[cn-1]
202 s= nCopy( q[cn-1] );
203
204 for ( k= cn-1; k >= 1; k-- ) { // k=cn; k >= 2
205 nDelete( &tmp1 );
206 tmp1= nMult( xx, b ); // b= c[k] + (xx * b)
207 nDelete( &b );
208 b= nAdd( c[k], tmp1 );
209
210 nDelete( &tmp1 );
211 tmp1= nMult( q[k-1], b ); // s= s + (q[k-1] * b)
212 newnum= nAdd( s, tmp1 );
213 nDelete( &s );
214 s= newnum;
215
216 nDelete( &tmp1 );
217 tmp1= nMult( xx, t ); // t= (t * xx) + b
218 newnum= nAdd( tmp1, b );
219 nDelete( &t );
220 t= newnum;
221 }
222
223 if (!nIsZero(t))
224 {
225 nDelete( &w[i] ); // w[i]= s/t
226 w[i]= nDiv( s, t );
227 nNormalize( w[i] );
228 }
229
231 }
232 }
233 mprSTICKYPROT("\n");
234
235 // free mem
236 for ( j= 0; j < cn; j++ ) nDelete( c+j );
237 omFreeSize( (void *)c, cn * sizeof( number ) );
238
239 nDelete( &tmp1 );
240 nDelete( &s );
241 nDelete( &t );
242 nDelete( &b );
243 nDelete( &xx );
244
245 // makes quotiens smaller
246 for ( j= 0; j < cn; j++ ) nNormalize( w[j] );
247
248 return w;
249}
int k
Definition: cfEzgcd.cc:99
CanonicalForm b
Definition: cfModGcd.cc:4103
const CanonicalForm int s
Definition: facAbsFact.cc:51
const CanonicalForm & w
Definition: facAbsFact.cc:51
#define mprSTICKYPROT(msg)
Definition: mpr_global.h:54
#define ST_VANDER_STEP
Definition: mpr_global.h:84
#define nDiv(a, b)
Definition: numbers.h:32
#define nInpNeg(n)
Definition: numbers.h:21
#define nIsZero(n)
Definition: numbers.h:19
#define nCopy(n)
Definition: numbers.h:15
#define nAdd(n1, n2)
Definition: numbers.h:18
#define nNormalize(n)
Definition: numbers.h:30
#define NULL
Definition: omList.c:12

◆ numvec2poly()

poly vandermonde::numvec2poly ( const number *  q)

Definition at line 93 of file mpr_numeric.cc.

94{
95 int j;
96 long i,/*c,*/sum;
97
98 poly pnew,pit=NULL;
99
100 // c=0;
101 sum=0;
102
103 int *exp= (int *) omAlloc( (n+1) * sizeof(int) );
104
105 for ( j= 0; j < n+1; j++ ) exp[j]=0;
106
107 for ( i= 0; i < l; i++ )
108 {
109 if ( (!homog || (sum == maxdeg)) && q[i] && !nIsZero(q[i]) )
110 {
111 pnew= pOne();
112 pSetCoeff(pnew,q[i]);
113 pSetExpV(pnew,exp);
114 if ( pit )
115 {
116 pNext(pnew)= pit;
117 pit= pnew;
118 }
119 else
120 {
121 pit= pnew;
122 pNext(pnew)= NULL;
123 }
124 pSetm(pit);
125 }
126 exp[1]++;
127 sum=0;
128 for ( j= 1; j < n; j++ )
129 {
130 if ( exp[j] > maxdeg )
131 {
132 exp[j]= 0;
133 exp[j + 1]++;
134 }
135 sum+= exp[j];
136 }
137 sum+= exp[n];
138 }
139
140 omFreeSize( (void *) exp, (n+1) * sizeof(int) );
141
142 pSortAdd(pit);
143 return pit;
144}
#define pNext(p)
Definition: monomials.h:36
#define pSetm(p)
Definition: polys.h:271
#define pSortAdd(p)
sorts p, p may have equal monomials
Definition: polys.h:221
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
#define pSetExpV(p, e)
Definition: polys.h:97
#define pOne()
Definition: polys.h:315

Field Documentation

◆ cn

long vandermonde::cn
private

Definition at line 50 of file mpr_numeric.h.

◆ homog

bool vandermonde::homog
private

Definition at line 57 of file mpr_numeric.h.

◆ l

long vandermonde::l
private

Definition at line 52 of file mpr_numeric.h.

◆ maxdeg

long vandermonde::maxdeg
private

Definition at line 51 of file mpr_numeric.h.

◆ n

long vandermonde::n
private

Definition at line 49 of file mpr_numeric.h.

◆ p

number* vandermonde::p
private

Definition at line 54 of file mpr_numeric.h.

◆ x

number* vandermonde::x
private

Definition at line 55 of file mpr_numeric.h.


The documentation for this class was generated from the following files: