Loading...
Searching...
No Matches
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.
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.

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

## ~vandermonde()

vandermonde::~vandermonde | ( |  | ) |

Definition at line 46 of file mpr_numeric.cc.

{
int j;
for ( j= 0; j < cn; j++ ) nDelete( x+j );
omFreeSize( (void *)x, cn * sizeof( number ) );
}
nDelete
#define nDelete(n)
Definition numbers.h:16
omFreeSize
#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.

{
int j;
long i,c,sum;
number tmp,tmp1;
c=0;
sum=0;
intvec exp( n );
for ( j= 0; j < n; j++ ) exp[j]=0;
for ( i= 0; i < l; i++ )
{
if ( !homog || (sum == maxdeg) )
{
for ( j= 0; j < n; j++ )
{
nPower( p[j], exp[j], &tmp );
tmp1 = nMult( tmp, x[c] );
x[c]= tmp1;
nDelete( &tmp );
}
c++;
}
exp[0]++;
sum=0;
for ( j= 0; j < n - 1; j++ )
{
if ( exp[j] > maxdeg )
{
exp[j]= 0;
exp[j + 1]++;
}
sum+= exp[j];
}
sum+= exp[n - 1];
}
}
i
int i
Definition cfEzgcd.cc:132
tmp1
CFList tmp1
Definition facFqBivar.cc:75
exp
gmp_float exp(const gmp_float &a)
Definition mpr_complex.cc:349
nMult
#define nMult(n1, n2)
Definition numbers.h:17
nPower
#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

  q | n-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.

{
int i,j,k;
number newnum,tmp1;
number b,t,xx,s;
number *c;
number *w;
b=t=xx=s=tmp1=NULL;
w= (number *)omAlloc( cn * sizeof(number) );
c= (number *)omAlloc( cn * sizeof(number) );
for ( j= 0; j < cn; j++ )
{
w[j]= nInit(0);
c[j]= nInit(0);
}
if ( cn == 1 )
{
nDelete( &w[0] );
w[0]= nCopy(q[0]);
}
else
{
nDelete( &c[cn-1] );
c[cn-1]= nCopy(x[0]);
c[cn-1]= nInpNeg(c[cn-1]); // c[cn]= -x[1]
for ( i= 1; i < cn; i++ ) { // i=2; i <= cn
if (xx!=NULL) nDelete( &xx );
xx= nCopy(x[i]);
xx= nInpNeg(xx); // xx= -x[i]
for ( j= (cn-i-1); j <= (cn-2); j++) { // j=(cn+1-i); j <= (cn-1)
if (tmp1!=NULL) nDelete( &tmp1 );
tmp1= nMult( xx, c[j+1] ); // c[j]= c[j] + (xx * c[j+1])
newnum= nAdd( c[j], tmp1 );
nDelete( &c[j] );
c[j]= newnum;
}
newnum= nAdd( xx, c[cn-1] ); // c[cn-1]= c[cn-1] + xx
nDelete( &c[cn-1] );
c[cn-1]= newnum;
}
for ( i= 0; i < cn; i++ ) { // i=1; i <= cn
nDelete( &xx );
xx= nCopy(x[i]); // xx= x[i]
if (t!=NULL) nDelete( &t );
t= nInit( 1 ); // t= b= 1
if (b!=NULL) nDelete( &b );
b= nInit( 1 );
if (s!=NULL) nDelete( &s ); // s= q[cn-1]
s= nCopy( q[cn-1] );
for ( k= cn-1; k >= 1; k-- ) { // k=cn; k >= 2
nDelete( &tmp1 );
tmp1= nMult( xx, b ); // b= c[k] + (xx * b)
nDelete( &b );
b= nAdd( c[k], tmp1 );
nDelete( &tmp1 );
tmp1= nMult( q[k-1], b ); // s= s + (q[k-1] * b)
newnum= nAdd( s, tmp1 );
nDelete( &s );
s= newnum;
nDelete( &tmp1 );
tmp1= nMult( xx, t ); // t= (t * xx) + b
newnum= nAdd( tmp1, b );
nDelete( &t );
t= newnum;
}
if (!nIsZero(t))
{
nDelete( &w[i] ); // w[i]= s/t
w[i]= nDiv( s, t );
nNormalize( w[i] );
}
mprSTICKYPROT(ST_VANDER_STEP);
}
}
mprSTICKYPROT("\n");
// free mem
for ( j= 0; j < cn; j++ ) nDelete( c+j );
omFreeSize( (void *)c, cn * sizeof( number ) );
nDelete( &tmp1 );
nDelete( &s );
nDelete( &t );
nDelete( &b );
nDelete( &xx );
// makes quotiens smaller
for ( j= 0; j < cn; j++ ) nNormalize( w[j] );
return w;
}
k
int k
Definition cfEzgcd.cc:99
b
CanonicalForm b
Definition cfModGcd.cc:4111
s
const CanonicalForm int s
Definition facAbsFact.cc:51
w
const CanonicalForm & w
Definition facAbsFact.cc:51
mprSTICKYPROT
#define mprSTICKYPROT(msg)
Definition mpr_global.h:54
ST_VANDER_STEP
#define ST_VANDER_STEP
Definition mpr_global.h:84
nDiv
#define nDiv(a, b)
Definition numbers.h:32
nInpNeg
#define nInpNeg(n)
Definition numbers.h:21
nIsZero
#define nIsZero(n)
Definition numbers.h:19
nCopy
#define nCopy(n)
Definition numbers.h:15
nAdd
#define nAdd(n1, n2)
Definition numbers.h:18
nNormalize
#define nNormalize(n)
Definition numbers.h:30
NULL
#define NULL
Definition omList.c:12

## numvec2poly()

poly vandermonde::numvec2poly | ( | const number * | q | ) |

Definition at line 93 of file mpr_numeric.cc.

{
int j;
long i,/*c,*/sum;
poly pnew,pit=NULL;
// c=0;
sum=0;
int *exp= (int *) omAlloc( (n+1) * sizeof(int) );
for ( j= 0; j < n+1; j++ ) exp[j]=0;
for ( i= 0; i < l; i++ )
{
if ( (!homog || (sum == maxdeg)) && q[i] && !nIsZero(q[i]) )
{
pnew= pOne();
pSetCoeff(pnew,q[i]);
pSetExpV(pnew,exp);
if ( pit )
{
pNext(pnew)= pit;
pit= pnew;
}
else
{
pit= pnew;
pNext(pnew)= NULL;
}
pSetm(pit);
}
exp[1]++;
sum=0;
for ( j= 1; j < n; j++ )
{
if ( exp[j] > maxdeg )
{
exp[j]= 0;
exp[j + 1]++;
}
sum+= exp[j];
}
sum+= exp[n];
}
omFreeSize( (void *) exp, (n+1) * sizeof(int) );
pSortAdd(pit);
return pit;
}
pNext
#define pNext(p)
Definition monomials.h:36
pSetm
#define pSetm(p)
Definition polys.h:272
pSortAdd
#define pSortAdd(p)
sorts p, p may have equal monomials
Definition polys.h:222
pSetCoeff
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition polys.h:32
pSetExpV
#define pSetExpV(p, e)
Definition polys.h:98
pOne
#define pOne()
Definition polys.h:316

## 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:

- kernel/numeric/mpr_numeric.h
- kernel/numeric/mpr_numeric.cc