My Project  UNKNOWN_GIT_VERSION
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 27 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 39 of file mpr_numeric.cc.

42  : n(_n), cn(_cn), maxdeg(_maxdeg), p(_p), homog(_homog)
43 {
44  long j;
45  l= (long)pow((double)maxdeg+1,(int)n);
46  x= (number *)omAlloc( cn * sizeof(number) );
47  for ( j= 0; j < cn; j++ ) x[j]= nInit(1);
48  init();

◆ ~vandermonde()

vandermonde::~vandermonde ( )

Definition at line 50 of file mpr_numeric.cc.

52 {
53  int j;
54  for ( j= 0; j < cn; j++ ) nDelete( x+j );
55  omFreeSize( (void *)x, cn * sizeof( number ) );

Member Function Documentation

◆ init()

void vandermonde::init ( )
private

Definition at line 57 of file mpr_numeric.cc.

59 {
60  int j;
61  long i,c,sum;
62  number tmp,tmp1;
63 
64  c=0;
65  sum=0;
66 
67  intvec exp( n );
68  for ( j= 0; j < n; j++ ) exp[j]=0;
69 
70  for ( i= 0; i < l; i++ )
71  {
72  if ( !homog || (sum == maxdeg) )
73  {
74  for ( j= 0; j < n; j++ )
75  {
76  nPower( p[j], exp[j], &tmp );
77  tmp1 = nMult( tmp, x[c] );
78  x[c]= tmp1;
79  nDelete( &tmp );
80  }
81  c++;
82  }
83  exp[0]++;
84  sum=0;
85  for ( j= 0; j < n - 1; j++ )
86  {
87  if ( exp[j] > maxdeg )
88  {
89  exp[j]= 0;
90  exp[j + 1]++;
91  }
92  sum+= exp[j];
93  }
94  sum+= exp[n - 1];
95  }

◆ 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 150 of file mpr_numeric.cc.

152 {
153  int i,j,k;
154  number newnum,tmp1;
155  number b,t,xx,s;
156  number *c;
157  number *w;
158 
159  b=t=xx=s=tmp1=NULL;
160 
161  w= (number *)omAlloc( cn * sizeof(number) );
162  c= (number *)omAlloc( cn * sizeof(number) );
163  for ( j= 0; j < cn; j++ )
164  {
165  w[j]= nInit(0);
166  c[j]= nInit(0);
167  }
168 
169  if ( cn == 1 )
170  {
171  nDelete( &w[0] );
172  w[0]= nCopy(q[0]);
173  }
174  else
175  {
176  nDelete( &c[cn-1] );
177  c[cn-1]= nCopy(x[0]);
178  c[cn-1]= nInpNeg(c[cn-1]); // c[cn]= -x[1]
179 
180  for ( i= 1; i < cn; i++ ) { // i=2; i <= cn
181  nDelete( &xx );
182  xx= nCopy(x[i]);
183  xx= nInpNeg(xx); // xx= -x[i]
184 
185  for ( j= (cn-i-1); j <= (cn-2); j++) { // j=(cn+1-i); j <= (cn-1)
186  nDelete( &tmp1 );
187  tmp1= nMult( xx, c[j+1] ); // c[j]= c[j] + (xx * c[j+1])
188  newnum= nAdd( c[j], tmp1 );
189  nDelete( &c[j] );
190  c[j]= newnum;
191  }
192 
193  newnum= nAdd( xx, c[cn-1] ); // c[cn-1]= c[cn-1] + xx
194  nDelete( &c[cn-1] );
195  c[cn-1]= newnum;
196  }
197 
198  for ( i= 0; i < cn; i++ ) { // i=1; i <= cn
199  nDelete( &xx );
200  xx= nCopy(x[i]); // xx= x[i]
201 
202  nDelete( &t );
203  t= nInit( 1 ); // t= b= 1
204  nDelete( &b );
205  b= nInit( 1 );
206  nDelete( &s ); // s= q[cn-1]
207  s= nCopy( q[cn-1] );
208 
209  for ( k= cn-1; k >= 1; k-- ) { // k=cn; k >= 2
210  nDelete( &tmp1 );
211  tmp1= nMult( xx, b ); // b= c[k] + (xx * b)
212  nDelete( &b );
213  b= nAdd( c[k], tmp1 );
214 
215  nDelete( &tmp1 );
216  tmp1= nMult( q[k-1], b ); // s= s + (q[k-1] * b)
217  newnum= nAdd( s, tmp1 );
218  nDelete( &s );
219  s= newnum;
220 
221  nDelete( &tmp1 );
222  tmp1= nMult( xx, t ); // t= (t * xx) + b
223  newnum= nAdd( tmp1, b );
224  nDelete( &t );
225  t= newnum;
226  }
227 
228  if (!nIsZero(t))
229  {
230  nDelete( &w[i] ); // w[i]= s/t
231  w[i]= nDiv( s, t );
232  nNormalize( w[i] );
233  }
234 
236  }
237  }
238  mprSTICKYPROT("\n");
239 
240  // free mem
241  for ( j= 0; j < cn; j++ ) nDelete( c+j );
242  omFreeSize( (void *)c, cn * sizeof( number ) );
243 
244  nDelete( &tmp1 );
245  nDelete( &s );
246  nDelete( &t );
247  nDelete( &b );
248  nDelete( &xx );
249 
250  // makes quotiens smaller
251  for ( j= 0; j < cn; j++ ) nNormalize( w[j] );
252 
253  return w;

◆ numvec2poly()

poly vandermonde::numvec2poly ( const number *  q)

Definition at line 97 of file mpr_numeric.cc.

99 {
100  int j;
101  long i,/*c,*/sum;
102 
103  poly pnew,pit=NULL;
104 
105  // c=0;
106  sum=0;
107 
108  int *exp= (int *) omAlloc( (n+1) * sizeof(int) );
109 
110  for ( j= 0; j < n+1; j++ ) exp[j]=0;
111 
112  for ( i= 0; i < l; i++ )
113  {
114  if ( (!homog || (sum == maxdeg)) && q[i] && !nIsZero(q[i]) )
115  {
116  pnew= pOne();
117  pSetCoeff(pnew,q[i]);
118  pSetExpV(pnew,exp);
119  if ( pit )
120  {
121  pNext(pnew)= pit;
122  pit= pnew;
123  }
124  else
125  {
126  pit= pnew;
127  pNext(pnew)= NULL;
128  }
129  pSetm(pit);
130  }
131  exp[1]++;
132  sum=0;
133  for ( j= 1; j < n; j++ )
134  {
135  if ( exp[j] > maxdeg )
136  {
137  exp[j]= 0;
138  exp[j + 1]++;
139  }
140  sum+= exp[j];
141  }
142  sum+= exp[n];
143  }
144 
145  omFreeSize( (void *) exp, (n+1) * sizeof(int) );
146 
147  pSortAdd(pit);
148  return pit;

Field Documentation

◆ cn

long vandermonde::cn
private

Definition at line 49 of file mpr_numeric.h.

◆ homog

bool vandermonde::homog
private

Definition at line 56 of file mpr_numeric.h.

◆ l

long vandermonde::l
private

Definition at line 51 of file mpr_numeric.h.

◆ maxdeg

long vandermonde::maxdeg
private

Definition at line 50 of file mpr_numeric.h.

◆ n

long vandermonde::n
private

Definition at line 48 of file mpr_numeric.h.

◆ p

number* vandermonde::p
private

Definition at line 53 of file mpr_numeric.h.

◆ x

number* vandermonde::x
private

Definition at line 54 of file mpr_numeric.h.


The documentation for this class was generated from the following files:
vandermonde::init
void init()
Definition: mpr_numeric.cc:57
nNormalize
#define nNormalize(n)
Definition: numbers.h:30
j
int j
Definition: facHensel.cc:105
k
int k
Definition: cfEzgcd.cc:92
vandermonde::maxdeg
long maxdeg
Definition: mpr_numeric.h:50
nPower
#define nPower(a, b, res)
Definition: numbers.h:38
nAdd
#define nAdd(n1, n2)
Definition: numbers.h:18
vandermonde::x
number * x
Definition: mpr_numeric.h:54
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
b
CanonicalForm b
Definition: cfModGcd.cc:4044
mprSTICKYPROT
#define mprSTICKYPROT(msg)
Definition: mpr_global.h:53
nInpNeg
#define nInpNeg(n)
Definition: numbers.h:21
ST_VANDER_STEP
#define ST_VANDER_STEP
Definition: mpr_global.h:83
i
int i
Definition: cfEzgcd.cc:125
omFreeSize
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:258
pSortAdd
#define pSortAdd(p)
sorts p, p may have equal monomials
Definition: polys.h:207
pOne
#define pOne()
Definition: polys.h:297
intvec
Definition: intvec.h:16
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:208
nDiv
#define nDiv(a, b)
Definition: numbers.h:32
tmp1
CFList tmp1
Definition: facFqBivar.cc:70
vandermonde::l
long l
Definition: mpr_numeric.h:51
pSetCoeff
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:30
exp
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
nIsZero
#define nIsZero(n)
Definition: numbers.h:19
nMult
#define nMult(n1, n2)
Definition: numbers.h:17
pow
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:414
NULL
#define NULL
Definition: omList.c:9
pSetm
#define pSetm(p)
Definition: polys.h:254
pSetExpV
#define pSetExpV(p, e)
Definition: polys.h:94
nDelete
#define nDelete(n)
Definition: numbers.h:16
vandermonde::homog
bool homog
Definition: mpr_numeric.h:56
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
nInit
#define nInit(i)
Definition: numbers.h:24
vandermonde::p
number * p
Definition: mpr_numeric.h:53
vandermonde::n
long n
Definition: mpr_numeric.h:48
nCopy
#define nCopy(n)
Definition: numbers.h:15
pNext
#define pNext(p)
Definition: monomials.h:34
vandermonde::cn
long cn
Definition: mpr_numeric.h:49