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.

  : 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();
}

~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 ) );
}

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];
  }
}

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;
}

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;
}

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