Skip to content

Linear (diophantine) and quadratic equations (spectral factorization) with univariate polynomials

License

Notifications You must be signed in to change notification settings

hurak/PolynomialEquations.jl

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

74 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

PolynomialEquations

Build Status Build Status Build Status Coverage Coverage Stable Dev

A Julia package for solving equations with univariate polynomials. Solvers for linear (Diophantine) equations (also called Bezout identity) in the ring of univariate polynomials and quadratic equations of special kind (also called spectral factorization) are (planned to be) provided.

It must be emphasized that the package does not offer functionality for solving nonlinear equations with the nonlinearities in the form of multivariate polynomials.

Available solvers

The equations currently solved by the package are

Homogeneous linear diophantine equation

$$a(s)x(s)+b(s)y(s) = 0$$

where a and b are given univariate polynomials in the variable s and x and y are the polynomials to be found.

Example

julia> a = Polynomial([1,2,3],:s);
julia> b = Polynomial([4,5],:s);
julia> c = Polynomial([1,1],:s);
julia> a = a*c;
julia> b = b*c;

julia> x, y = axby0(a,b)
(Polynomial(-0.5393598899705949 - 0.6741998624632413*s), Polynomial(0.1348399724926485 + 0.2696799449852973*s + 0.4045199174779448*s^2))

julia> a*x+b*y
Polynomial(-8.881784197001252e-16 - 4.440892098500626e-16*s - 8.881784197001252e-16*s^2 - 8.881784197001252e-16*s^3)

Linear diophantine equation

$$a(s)x(s)+b(s)y(s) = c(s)$$

where a, b and c are given univariate polynomials in the variable s and x and y are the polynomials to be found.

Example

julia> a = Polynomial([1,2,3],:s);
julia> b = Polynomial([4,5],:s);
julia> c = Polynomial([6,7,8,9],:s);

julia> x,y = axbyc(a,b,c)
(Polynomial(3.0909090909090913 + 3.0*s), Polynomial(0.7272727272727273 - 1.4545454545454548*s))

julia> a*x+b*yc
true

Symmetrix conjugate equation (continuous-time case)

$$a(s)x(-s)+a(-s)x(s) = b(s)+b(-s)$$

where a, b and c are given univariate polynomials in the variable s and x and y are the polynomials to be found.

If the coefficients of the polynomials are complex, then not only -s is substituted for s but also the coefficients are complex-conjugated.

Formally, both real and complex cases are captured in the following notation

$$a(s)x̃(s)+ã(s)x(s) = b(s)+b̃(s)$$

where tilde denotes conjugation of a polynomial with respect to the imaginary axis, that is, the conjugate polynomial evaluates to a complex conjugate value of the original polynomial on the imaginary axis.

Example

julia> a = Polynomial([-0.12, -0.29, 1],:s);
julia> b = Polynomial([1.86, -0.34, -1.14, -0.21, 1.19, -1.12],:s);

julia> x = axaxbb(a,b)
Polynomial(-15.50000000000003 + 50.0096551724139*s + 1.19*s^2)

julia> cconj(a)*x+a*cconj(x)b+cconj(b)
true

Nonsymmetric conjugate equation (continuous-time case)

As a generalization of the previous symmetric conjugate equation, there is also a solver for a nonsymmetric conjugation.

$$a(s)x(-s)+b(-s)y(s) = c(s)+d(-s)$$

Example

julia> a = Polynomial([-0.12, -0.29, 1],:s);
julia> b = Polynomial([1.86, -0.34, -1.14, -0.21, 1.19, -1.12],:s);
julia> c = Polynomial([1.2, 3.4, 5.6],:s);
julia> d = Polynomial([3.4, 5.6, 6.7, 7.8, 8.9, 9.1, 1.2],:s);

julia> x,y = axbycd(a,b,c,d)
(Polynomial(13.57846778138169 + 9.81569937794185*s + 1.6765177065455532*s^2 + 12.031635021058513*s^3 + 1.5485480613952116*s^4), Polynomial(3.349148459013872 - 0.31120362624572473*s))

julia> a*cconj(x)+cconj(b)*yc+cconj(d)
true

To do

The symmetric and nonsymmetric conjugate equations for Laurent polynomials

$$a(z)x(1/z)+b(1/z)y(z) = c(z)+d(1/z)$$

and

$$a(z)x(1/z)+a(1/z)x(z) = b(z)+b(1/z)$$

in which a, b and c are given polynomials and x and y are the polynomials to be found.

A plan is to implement some solver(s) for the quadratic equations too, namely the equations of the type

$$a(s)a(-s) = x(-s)x(s)$$

and

$$a(z)a(1/z) = x(z)x(1/z)$$

where a is some given univariate polynomial and x is a Hurwitz stable and Schur stable polynomial, respectively, That is, all its roots are inside the open left half plane and the open unit disk, respectively.

Related Julia packages

  • Polynomials – provides the basic data types – Polynomial and LaurentPolynomial.
  • PolynomialMatrices – a package defining a new data type – a polynomial matrix (or matrix polynomial). In principle, many if not all equations with polynomials can be reformulated as equations with polynomial matrices. For example, the equation ax+by=0 can be formulated as [a b][x;y]=0, that is, a polynomial nullspace problem Az=0, or similarly ax+by=c can be rewritten as Az=c, therefore developing dedicated scalar versions of solvers might be viewed as redundant. Still, in many projects scalar polynomials are used exclusively (SISO filter and controller design) and avoiding the complications with polynomial matrices is useful.
  • ControlSystems – a package for control system design. This package and the next might be finally benefitting from the PolynomialEquations package. Some solver for linear diophantine equation with univariate polynomials is already implemented in ControlSystems package, namely the dab function, but others are missing.
  • DSP – a package for digital signal processing.

Related other software packages

About

Linear (diophantine) and quadratic equations (spectral factorization) with univariate polynomials

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages