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 {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 48 of file mpr_numeric.cc.

50  : n(_n), cn(_cn), maxdeg(_maxdeg), p(_p), homog(_homog)
51 {
52  long j;
53  l= (long)pow((double)maxdeg+1,(int)n);
54  x= (number *)omAlloc( cn * sizeof(number) );
55  for ( j= 0; j < cn; j++ ) x[j]= nInit(1);
56  init();
57 }
void init()
Definition: mpr_numeric.cc:66
#define omAlloc(size)
Definition: omAllocDecl.h:210
number * x
Definition: mpr_numeric.h:55
int j
Definition: myNF.cc:70
number * p
Definition: mpr_numeric.h:54
#define nInit(i)
Definition: numbers.h:24
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:418

§ ~vandermonde()

vandermonde::~vandermonde ( )

Definition at line 59 of file mpr_numeric.cc.

60 {
61  int j;
62  for ( j= 0; j < cn; j++ ) nDelete( x+j );
63  omFreeSize( (void *)x, cn * sizeof( number ) );
64 }
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
number * x
Definition: mpr_numeric.h:55
int j
Definition: myNF.cc:70
#define nDelete(n)
Definition: numbers.h:16

Member Function Documentation

§ init()

void vandermonde::init ( )
private

Definition at line 66 of file mpr_numeric.cc.

67 {
68  int j;
69  long i,c,sum;
70  number tmp,tmp1;
71 
72  c=0;
73  sum=0;
74 
75  intvec exp( n );
76  for ( j= 0; j < n; j++ ) exp[j]=0;
77 
78  for ( i= 0; i < l; i++ )
79  {
80  if ( !homog || (sum == maxdeg) )
81  {
82  for ( j= 0; j < n; j++ )
83  {
84  nPower( p[j], exp[j], &tmp );
85  tmp1 = nMult( tmp, x[c] );
86  x[c]= tmp1;
87  nDelete( &tmp );
88  }
89  c++;
90  }
91  exp[0]++;
92  sum=0;
93  for ( j= 0; j < n - 1; j++ )
94  {
95  if ( exp[j] > maxdeg )
96  {
97  exp[j]= 0;
98  exp[j + 1]++;
99  }
100  sum+= exp[j];
101  }
102  sum+= exp[n - 1];
103  }
104 }
#define nPower(a, b, res)
Definition: numbers.h:38
number * x
Definition: mpr_numeric.h:55
Definition: intvec.h:14
int j
Definition: myNF.cc:70
#define nMult(n1, n2)
Definition: numbers.h:17
int i
Definition: cfEzgcd.cc:123
#define nDelete(n)
Definition: numbers.h:16
CFList tmp1
Definition: facFqBivar.cc:70
p exp[i]
Definition: DebugPrint.cc:39
number * p
Definition: mpr_numeric.h:54

§ interpolateDense()

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

Solves the Vandermode linear system {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 159 of file mpr_numeric.cc.

160 {
161  int i,j,k;
162  number newnum,tmp1;
163  number b,t,xx,s;
164  number *c;
165  number *w;
166 
167  b=t=xx=s=tmp1=NULL;
168 
169  w= (number *)omAlloc( cn * sizeof(number) );
170  c= (number *)omAlloc( cn * sizeof(number) );
171  for ( j= 0; j < cn; j++ )
172  {
173  w[j]= nInit(0);
174  c[j]= nInit(0);
175  }
176 
177  if ( cn == 1 )
178  {
179  nDelete( &w[0] );
180  w[0]= nCopy(q[0]);
181  }
182  else
183  {
184  nDelete( &c[cn-1] );
185  c[cn-1]= nCopy(x[0]);
186  c[cn-1]= nInpNeg(c[cn-1]); // c[cn]= -x[1]
187 
188  for ( i= 1; i < cn; i++ ) { // i=2; i <= cn
189  nDelete( &xx );
190  xx= nCopy(x[i]);
191  xx= nInpNeg(xx); // xx= -x[i]
192 
193  for ( j= (cn-i-1); j <= (cn-2); j++) { // j=(cn+1-i); j <= (cn-1)
194  nDelete( &tmp1 );
195  tmp1= nMult( xx, c[j+1] ); // c[j]= c[j] + (xx * c[j+1])
196  newnum= nAdd( c[j], tmp1 );
197  nDelete( &c[j] );
198  c[j]= newnum;
199  }
200 
201  newnum= nAdd( xx, c[cn-1] ); // c[cn-1]= c[cn-1] + xx
202  nDelete( &c[cn-1] );
203  c[cn-1]= newnum;
204  }
205 
206  for ( i= 0; i < cn; i++ ) { // i=1; i <= cn
207  nDelete( &xx );
208  xx= nCopy(x[i]); // xx= x[i]
209 
210  nDelete( &t );
211  t= nInit( 1 ); // t= b= 1
212  nDelete( &b );
213  b= nInit( 1 );
214  nDelete( &s ); // s= q[cn-1]
215  s= nCopy( q[cn-1] );
216 
217  for ( k= cn-1; k >= 1; k-- ) { // k=cn; k >= 2
218  nDelete( &tmp1 );
219  tmp1= nMult( xx, b ); // b= c[k] + (xx * b)
220  nDelete( &b );
221  b= nAdd( c[k], tmp1 );
222 
223  nDelete( &tmp1 );
224  tmp1= nMult( q[k-1], b ); // s= s + (q[k-1] * b)
225  newnum= nAdd( s, tmp1 );
226  nDelete( &s );
227  s= newnum;
228 
229  nDelete( &tmp1 );
230  tmp1= nMult( xx, t ); // t= (t * xx) + b
231  newnum= nAdd( tmp1, b );
232  nDelete( &t );
233  t= newnum;
234  }
235 
236  if (!nIsZero(t))
237  {
238  nDelete( &w[i] ); // w[i]= s/t
239  w[i]= nDiv( s, t );
240  nNormalize( w[i] );
241  }
242 
244  }
245  }
246  mprSTICKYPROT("\n");
247 
248  // free mem
249  for ( j= 0; j < cn; j++ ) nDelete( c+j );
250  omFreeSize( (void *)c, cn * sizeof( number ) );
251 
252  nDelete( &tmp1 );
253  nDelete( &s );
254  nDelete( &t );
255  nDelete( &b );
256  nDelete( &xx );
257 
258  // makes quotiens smaller
259  for ( j= 0; j < cn; j++ ) nNormalize( w[j] );
260 
261  return w;
262 }
#define mprSTICKYPROT(msg)
Definition: mpr_global.h:54
const CanonicalForm int s
Definition: facAbsFact.cc:55
#define ST_VANDER_STEP
Definition: mpr_global.h:84
#define nNormalize(n)
Definition: numbers.h:30
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
int k
Definition: cfEzgcd.cc:93
#define omAlloc(size)
Definition: omAllocDecl.h:210
number * x
Definition: mpr_numeric.h:55
int j
Definition: myNF.cc:70
#define nInpNeg(n)
Definition: numbers.h:21
#define nMult(n1, n2)
Definition: numbers.h:17
int i
Definition: cfEzgcd.cc:123
#define nDelete(n)
Definition: numbers.h:16
#define nDiv(a, b)
Definition: numbers.h:32
#define nIsZero(n)
Definition: numbers.h:19
#define NULL
Definition: omList.c:10
CFList tmp1
Definition: facFqBivar.cc:70
const CanonicalForm & w
Definition: facAbsFact.cc:55
#define nCopy(n)
Definition: numbers.h:15
#define nInit(i)
Definition: numbers.h:24
const poly b
Definition: syzextra.cc:213
#define nAdd(n1, n2)
Definition: numbers.h:18

§ numvec2poly()

poly vandermonde::numvec2poly ( const number *  q)

Definition at line 106 of file mpr_numeric.cc.

107 {
108  int j;
109  long i,/*c,*/sum;
110 
111  poly pnew,pit=NULL;
112 
113  // c=0;
114  sum=0;
115 
116  int *exp= (int *) omAlloc( (n+1) * sizeof(int) );
117 
118  for ( j= 0; j < n+1; j++ ) exp[j]=0;
119 
120  for ( i= 0; i < l; i++ )
121  {
122  if ( (!homog || (sum == maxdeg)) && q[i] && !nIsZero(q[i]) )
123  {
124  pnew= pOne();
125  pSetCoeff(pnew,q[i]);
126  pSetExpV(pnew,exp);
127  if ( pit )
128  {
129  pNext(pnew)= pit;
130  pit= pnew;
131  }
132  else
133  {
134  pit= pnew;
135  pNext(pnew)= NULL;
136  }
137  pSetm(pit);
138  }
139  exp[1]++;
140  sum=0;
141  for ( j= 1; j < n; j++ )
142  {
143  if ( exp[j] > maxdeg )
144  {
145  exp[j]= 0;
146  exp[j + 1]++;
147  }
148  sum+= exp[j];
149  }
150  sum+= exp[n];
151  }
152 
153  omFreeSize( (void *) exp, (n+1) * sizeof(int) );
154 
155  pSortAdd(pit);
156  return pit;
157 }
#define pSetm(p)
Definition: polys.h:253
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omAlloc(size)
Definition: omAllocDecl.h:210
int j
Definition: myNF.cc:70
#define pSetExpV(p, e)
Definition: polys.h:97
int i
Definition: cfEzgcd.cc:123
#define pOne()
Definition: polys.h:297
#define pSortAdd(p)
sorts p, p may have equal monomials
Definition: polys.h:204
#define nIsZero(n)
Definition: numbers.h:19
#define NULL
Definition: omList.c:10
#define pNext(p)
Definition: monomials.h:43
p exp[i]
Definition: DebugPrint.cc:39
polyrec * poly
Definition: hilb.h:10
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31

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: