Click here to Skip to main content
Click here to Skip to main content

Multivariate polynomial

, 17 Dec 2012
Rate this:
Please Sign up or sign in to vote.
Implement a multivariate polynomial class for a large number of terms.

Introduction

Multivariate Polynomial is a C# class library providing basic polynomial arithmetics such as addition, multiplication and exponentiation, differentiation by one variable , Division by one term polynomial and evaluation by get variable and it's value.

Multivariate polynomial definition:

F(x,y,z,k,l)=2.2xy1.2z6k-5

A polynomial that multivarates, look at this grammar definition :

multivariate polynomial structure is :

E1[+/-]E2[+/-]E3…[+/-]En

that E is

[R][a…z][R][a…z][R]…[a…z][R]

and R is

[N].[N] or [N]

and in other hand a multivariate polynomial is terms that each term is a function of some variable

Example:

23.42bd5.3fgh3j3s1.43+d3f3s3+4x+3432432
23.42bd5.3fgh3j3s1.43+d3f3s3+4x+3432432
d3f3s4-34e3r4w10
796.28bd5.3e3fgh3j3r4s1.43w10-23.42bd5.3fgh3j3s1.43-34d3e3f3r4s3w10
          +d3f3s3+3432432d3f3s4+4d3f3s4x-116702688e3r4w10-136e3r4w10x

This class implements operators and polynomial string readers and you can calculate polynomial operations simply the same as scalar variables:

P1=p2*p3+p4/p5+p6;
P2=(p1/p2*p4)/p7-p12+p2;

My goal in this class is to implement a multivarate polynomial class for large number of terms for example 50000, and using structures for memory usage and speed (low complexity).

For this reason I implement a polynomial term array and control it using a heap structure .

Heap structure is a continuous memory that that does not have any gap in the array and results in speedy access.

This class implements:

  1. Read and get string format of polynomial in sorted way (standard writing)
  2. Control memory usage
  3. Ease of use
  4. Take care about class structure and its separation
  5. Find term in from log n to N at most complexity
  6. Insert terms in log N complexity
  7. Get memory for terms when it needed
  8. Write ToString in all subclass levels to multivariate polynomial
  9. Sorting term laws:
    • From left to right in 2 term , from less character variable code ( comparing variables)
    • In equal variable name less power is first

Using the code

Object definition :

MutliVariantPolynomial ff=new MutliVariantPolynomial(50000); 

This constructor gets maximum term number and builds a refrence polynomial term array

or

MutliVariantPolynomial ff=MutliVariantPolynomial("2.2xy1.2z6k-5",10000) 

this constructor build polynomial with polynomial string that describe in introduction

Points of Interest

this class for fast sorting and build strings and add terms , define some property in multivariate polynomial such as TermVarString and TermString :

TermVarString: a sring that build from concatenation of term variables ( in sorted order)

TermString: a sring that build from concatenation of term variables and It's power( in sorted order and rounded power in fixed point number)

CompareTo Method in PolynomTerm:

internal int CompareTo(PolynomTerm polynomTerm)
{
    if (termVarString != polynomTerm.termVarString)
    {
        if(termVarString=="")
            return 1;
        if (polynomTerm.termVarString == "")
            return -1;
    }

    int mogh=termVarString.CompareTo(polynomTerm.termVarString);
    if (mogh >0)
        return 1;
    if (mogh<0)
        return -1;

    foreach (char ch in termVarString)
    {
        if (termPartials[ch - 'a'].pow > polynomTerm.termPartials[ch - 'a'].pow)
            return 1;
        if (termPartials[ch - 'a'].pow < polynomTerm.termPartials[ch - 'a'].pow)
            return -1;
    }

    return 0;
}

and smallest priority is empty TermVarString or constants.

The classes that are implemented in this project is:

Constants: Define Static Constants for other class using

TermPartial: x2 and y1.2 and z is termpartial of -4x2y1.2z and this class goal is manage termpartial

PolynomTerm: manage one term in polynomial : [R][a…z][R][a…z][R]…[a…z][R] that contain one coefficient and one array of termpartial.

MutliVariantPolynomial: manage last polynomial that contain some PolynomTerm object in array and it's insert and delete and find and tostring operation implemented by heap structure.

Example of InsertTerm code in MultivaratePolynomial class that inserts a new term in polynomial is :

bool InsertTerm(PolynomTerm x)
{
    int i;
    PolynomTerm pt;
    if (cntTerm == maxTerm)
        return false;
    else
    {
        cntTerm++;
        i = cntTerm;
        terms[cntTerm] = x.Clone();
        while (true)
        {
            if (i == 1)
                break;
            if (terms[i].CompareTo(terms[i / 2]) >= 0)
                break;
            pt = terms[i];
            terms[i] = terms[i / 2];
            terms[i / 2] = pt;
            int kk = i;
            i = i / 2;
            if (kk % 2 == 0)
            {
                if (kk < cntTerm)
                    if (terms[kk].CompareTo(terms[kk + 1]) > 0)
                    {
                        pt = terms[kk];
                        terms[kk] = terms[kk + 1];
                        terms[kk + 1] = pt;
                    }
            }
            else if (kk != 1)
                if (terms[kk - 1].CompareTo(terms[kk]) > 0)
                {
                    pt = terms[kk - 1];
                    terms[kk - 1] = terms[kk];
                    terms[kk] = pt;
                }
        }
        terms[i] = x.Clone();
        return true;
    }
}

History:

Version 1.0

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author


Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Mobile
Web01 | 2.8.140827.1 | Last Updated 17 Dec 2012
Article Copyright 2012 by mojtaba mahdavi software dev
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid