Complex polynomials

[projekter]

I would like to discuss your thoughts and possibilities to add more support for complex-valued variables to the polynomials. This was already partially mentioned in #11 (conjugation). In #116, it was mentioned that conjugation of variables is not an algebraic operation and therefore should not be considered at all; but while this is a package in JuliaAlgebra, the package description is quite general and support for this would be helpful in some instances, so I hope we can have a fruitful discussion.

Let me first give the example why this is important for me: Of course, one can easily say that every complex variable is just the sum of two real variables with complex coefficients (and since coefficients are generic, this is already implemented). However, in some instances it might be helpful to consider the complex variables and their conjugates instead of the real and imaginary part as the "intrinsic" variables of the polynomial. In particular, there is a relatively recent approach to polynomial optimization, where different relaxation hierarchies arise depending on whether the one or the other way of seeing things are used.

Here are some thoughts on what I think would be useful to have (in fact, I implemented all of this and hacked an extension to DynamicPolynomials; and I am using it successfully in my optimization code - but it is a hack, is architecture-dependent at the moment, is not terribly efficient, and would be pretty impossible to define in a package, so I just provide the code in this Gist):

• Variables should have a status of whether they would be affected by all the operations that I'll talk about below.
  This is more on the side of implementations, e.g., in DynamicPolynomials we already declare variables via @polyvar and @ncpolyvar, so I chose @polycvar (and probably @ncpolycvar, though I did not consider the non-commuting case) - but perhaps a keyword parameter would be more suitable if further additions would come along, as discussed in Conjugation and Hermitian variables #11).
  All the functions where this would make a difference are not implemented yet, so either choice as default should not affect backwards-compatibility. However, choosing variables not to be complex by default allows all packages that use this interface to work as before, and only if they decide to add support for this, they have to overwrite the basic definitions on the variable level.
• Provide a querying function à la iscomplex(::AbstractVariable), defined by the particular implementation, and a generic implementation for all other types (though what would this return for a real-valued polynomial with complex coefficients - as coefficients can be anything, they should not be considered). Probably the mouthful hascomplexvars would better describe the purpose?
• Appropriately define Base.conj, Base.real, and Base.imag (and LinearAlgebra.adjoint) for AbstractVariable.
  This implies that a complex variable can have four different states: its original value, its conjugated value, its real part, or its imaginary part (if we go to the extreme, also magnitude and phase, but this is probably not used ever in polynomial contexts and could provide some problems on how to extend the functions to higher-level constructs).
  Although all four are different, they are related: For example, the real part of the variable should be equal to (==) the real part of its conjugate. Or substitution should be possible by specifying either of the four (possibly leading to partial substitution). Printing should be done appropriately, and a helper function (which I called ordvar) that goes back from any of the four to the original variable would be helpful. Provide querying functions such as isrealpart, isimagpart, isconj - or perhaps just some complextype that gives an enumeration?
• Debatable: Provide something like the complex-valued degree of a polynomial. For each monomial, this is the maximum of the degree of the variables or the degree of the conjugate variables. However, it would in principle be possible to mix this with real and imaginary parts, then something like this would be undefined.
• Easy and unambiguous: Generically extend conj for all higher-level constructs (monomials, terms, polynomials). At least, this is easy if we don't accept the magnitude/phase states as valid.
• Debatable: Generically define real and imag for all higher-level constructs. I can see two ways: Either go back to the level of variables and express everything in terms of the real and imaginary parts of the variables, then give back the appropriate result (this will expand complex monomials). Or provide the same extension as for variables also for monomials - namely, that a monomial can refer to its original value, its conjugate value (which could/should? be propagated to the variables), or its real or imaginary part, without expanding.

The reason why I implemented this in such a hacky way is that pretty much all the functions that work perfectly for PolyVar would work in the exact same way for the complex PolyVar - so subtyping it would be the best "noninvasive" way, were it an abstract type. The reason why performance is suboptimal is mainly the inefficient conj function for monomials.

[blegat]

Hi, implementing this would be great. it could be part of a new implementation of MultivariatePolynomials, a proof of concept would be great.
Creating new implementaitons of MultivariatePolynomials is now much easier thanks to #199

[projekter]

Ok, I created #213 as a first draft for these ideas, only the MultivariatePolynomial side. Some (debatable) design decisions:

• I put most of the code in a new complex.jl file, though some of may perhaps be better suited for other files such as variable.jl or operators.jl.
• Variables can be complex-valued, their conjugates and their real and imaginary parts. I did not define those properties for higher-level constructs such as monomials. In my own SOS solver, I actually also need a "monomial wrapper" that corresponds to the real/imaginary part of a monomial instead of breaking it down into real/imaginary parts of the variables. While this would also be a nice feature to have, the question is then what real and imag should do. Probably an approach as in Mathematica would be meaningful, i.e., to have a ComplexExpand equivalent that breaks down everything in terms of real-valued variables.
• I don't know how and if this integrates with the default implementations for terms and/or polynomials. Actually, what is affected here are mainly the variables (for which there is no default implementation AFAIK), and once support for a complex-valued variable is provided by an implementation, the generic functions mostly do the job.

Once/if the design decisions for the MultivariatePolynomial interface are sufficiently clear, I can also provide a draft for a possible DynamicPolynomials implementation (I don't think a "new" implementation would be needed, as this should really seamlessly integrates with the existing ones without any compatibility-breaking change - so a new implementation would include lots of redundant code from whatever it builds on).