Why Does polyval Return Zero When the Coefficients are Empty?

polyval([],1)

ans = 0

polyval(ones(1,0),1)

ans = 0

Do those results follow from a mathematical justification or are they arbitrarily specified?

Answer 1

[dpb]

Boils down to applying Horner's rule with internal function that ends up at

function y = iHorner(x, p)
% Apply Horner's method to calculate the value of polynomial p at x.
if isempty(p)
    y = zeros(size(x), 'like', x);
    return
end

It follow the convention that a missing coefficient in a polynomial is zero such that one can write

y=3x^2 + 1

with the meaning being that of

y=3x^2 + 0x + 1

Without the convention one also would have to start with the x^N where N was some large integer with a zillion terms with zero coefficients.

[Catalytic]

Even if polyval were to use a more naive polynomial evaluation algorithm than Horner, its operator rules give the same --

compareThem([5,2,4])

res1 = 263

res2 = 263

compareThem([])

res1 = 0

res2 = 0

function compareThem(p)

   x=7;
   n=numel(p);
   
   res1 = polyval(p,x)
   
   res2=x.^(n-1:-1:0)*p(:)
   
end

Answer 2

[Matt J]

For non-empty A and B, we have the general relation,

polyval([A,B],z)=polyval(A,z)*z^numel(B) + polyval(B,z)

Extending this to B=[] would reduce it to,

polyval([A,[]],z) = polyval(A,z)*z^0 + polyval([],z)
      polval(A,z) = polyval(A,z)*1 + polyval([],z)

Solving for polyval([],z) then leads to,

                 polyval([],z)=0

[Paul]

Execellent.

Following that line of reasoning, I suppose that's why

poly([])

ans = 1

That is, for A,B square matrices, we must have

poly(blockdiag(A,B)) = conv(poly(A),poly(B))

with B = []

poly(blockdiag(A,[])) = poly(A) = conv(poly(A),poly([])) -> poly([]) = 1

[Matt J]

That is indeed consistent, but I think you could also argue that a polynomial with an empty set of roots has to be a constant, and the constant polynomial with a leading coefficient of one is 1.

[Paul]

I was originally thinking along those lines. The doc page for poly shows two usages:

p = poly(r), where r is a vector, returns the coefficients of the polynomial whose roots are the elements of r.

p = poly(A), where A is an n-by-n matrix, returns the n+1 coefficients of the characteristic polynomial of the matrix, det(λI – A).

But [] is a matrix, not a vector, so I focused on the second usage

A = [];
[isvector(A),ismatrix(A)]

ans = 1×2 logical array
   0   1

OTOH, if we start with an empty vector

r = ones(1,0);
isvector(r)

ans = logical
   1

then we have for the first usage

poly(r)

ans = 1

I suppose that the poly(r) case could return any constant. I didn't see anything at poly that says the output of poly(r) has to have a leading coeffcient of 1. However, the poly(A) case must return 1.

I'm pretty sure that poly always returns p with leading coefficient of 1, and the doc page should say so for the first usage, e.g., "returns the coefficients of the polynomial with leading coefficient of 1 whose roots are the elements of r."

[Paul]

Given

V = [1,2]; R = double.empty(1,0);
conv(V,0)

ans = 1×2

0 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

Then the output of conv for this case

conv(V,R)  % R treated like the zero-polynomial

ans = 1×2

0 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

doesn't seem to be consistent with

conv(R,R) % should return 0?

ans =

  1×0 empty double row vector

which is in turn not consistent with

[q,d] = polyder(V,R)  % d should be conv(R,R)

q = 0

d = 0

I'm thinking that conv(R,R) should be 0.

[Matt J]

I don't know if I agree that R is equivalent to the zero-polynomial. That would be like saying, sum([])=0 implies that []=0.

[Paul]

I meant that R is like the zero polynominal specifically in the case of conv (and polyval and polyder and polyint for that matter). Didn't intend to extend that line of thought to other usages of empty objects.

What do you think the output of conv(R,R) should be?

[Matt J]

I would have thought conv(R,R)=1, based on the identity,

conv(A,B)=poly([roots(A);roots(B)])

A=[1,rand(1,3)]; B=[1,rand(1,3)];

poly([roots(A);roots(B)])

ans = 1×7

1.0000 0.6152 1.1333 0.5778 0.3343 0.1314 0.0102

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

conv(A,B)

ans = 1×7

1.0000 0.6152 1.1333 0.5778 0.3343 0.1314 0.0102

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

R = double.empty(1,0);
poly([roots(R);roots(R)])

ans = 1

Answer 3

[John D'Errico]

(This could easily better belong in a discussion than in Answers.)

I could argue that any choice they made was arbitrary, because I'm not sure a null polynomial has what I'd call a good formal mathematical definition. In some sense I might want to argue the prediction from a empty set polynomial should be an empty set. That is, should there be a distinction in the prediction of these two "polynomials", P0 and Pnull?

P0 = 0;

and

Pnull = [];

A meta-rule in MATLAB is that empty generally produces empty in MATLAB. For example:

max([])

ans =

     []

Ok, so what does a null set polynomial mean? I threw this into an AI tool, to see if there was something well known I might be missing. Google suggests:

"A polynomial described as the null set polynomial (or more commonly, a polynomial whose set of roots is the null set/empty set, ∅.

This means a polynomial that has no roots(no zeros) within a specified field of numbers, such as the real numbers ℝ."

(I also put the same question to ChatGPT, which essentially concurs with Google, but it also agreed with my intuitive assertion that a null polynomial has no strong formal definition in mathematics.)

In MATLAB of course, we would think of such a polynomial as one which has no roots in the complex plane. Continuing along those lines, that would make a distinction between the zero and null polynomials, where the zero polynomial has infinitely many roots in both the real line and in the complex plane.

Again, I think this argues for a null result from polyval for a null input poly, even though polyval disagrees.

polyval(P0,1),polyval(Pnull,1)

ans = 0

ans = 0

Looking at the answer from @dpb, I first see the argument the polynomial 3*x^2 + 1 has a zero linear coefficient, so when no coefficient is provided, we presume zero. And while I think this makes sense, that seems different from the case where no polynomial is provided at all.

I think a better argument is made when @dpb points out the Matlab convention about higher order coefficients being presumed as zero. That is

P2 = [3 0 1];

P2 is a quadratic polynomial, so that all higher order coefficients are implicitly zero. Thus the coefficient of x^3 is presumed to be zero. If we continue along that line of reasoning, the polynomial P0, with only a zero constant term, has all higher order coefficients as zero.

But now drop away the constant coefficient, and apply the same reasoning. That is, all higher order (unsupplied) coefficients are implicitly zero, which arguably applies even to the constant coefficient. And that suggests the null polynomial would have an implicit zero constant term coefficient. I'd suggest this is mathematically equivalent to the answer from @Matt J, where he extrapolates down to the null polynomial via Horner's rule.

Is the application of Horner's rule a good argument in this? Well, yes, since polyval explicitly does use Horner's rule to evaluate the polynomial.

In the end, as I said, the answer is a little arbitrary, but I think zero as the prediction for polyval([],1) makes sense.

[Paul]

All good points.

"A meta-rule in MATLAB is that empty generally produces empty in MATLAB."

Empty doesn't produce empty for some linear algebra operations (like mtimes, of which I'm not 100% comfortable), logical operations (like any and all), arithmetic operations (like sum and prod), and polynomial operations (poly as discussed here, and polyder as I just discovered), and (maybe?) other types of operations. Mathworks has attempted to bring formalism to the definition of empty within Matlab, even if, as you say, a formal mathematical definition is lacking.

From a user/programmer perspective, I think it's better to assume that empty never produces empty, and one must guard against that behavior if it's not desired.

[dpb]

I wasn't intendeing the code snippet to be a justification, just showing how/where MATLAB did the deed.

And I don't disagree about the stance on defensive programming regarding results of empty arguments although my practice is to make the check/fixup on the input side rather than waiting to discover something unexpected happened at the output.

[Matt J]

A meta-rule in MATLAB is that empty generally produces empty in MATLAB.

That rule applies to binary operators, but seemingly not to iterative reduction operators. So, for example,

[] + []

ans =

     []

[] .* []

ans =

     []

but, their corresponding iterative extensions give non-empty results,

sum([ [] , [] ])

ans = 0

prod([ [] , [] ])

ans = 1

So, I suppose polyval is classified as an iterative reduction operator.

[Paul]

"That rule applies to binary operators, ..."

Not always, at least not for empty vectors

R = double.empty(1,0);
R*R'

ans = 0

[John D'Errico]

"So, I suppose polyval is classified as an iterative reduction operator."

My guess is, there was never an explicit classification done of polyval as an operator. Or of exactly how polyval should operate on an empty polynomial. Given that polyval probably goes back to version 1 of MATLAB as written roughly in 1984, and it used Horner's method even then, nobody worried about it then, and nobody ever really worried about it in the 40+ years since. The Horner loop naturally produces zero as a result for empty polynomials. And it is likely true nobody was going to modify the behavior of polyval over that period unless they had some good reason. TMW tries to never damage legacy code if possible, and an arbitrary change to polyval at some point could easily do that for no good reason.

[Matt J]

I don't think A*B' would actually fall into the same category of binary operators as times(A,B), since for non-empty vector operands A and B, one is a reduction and the other is not. The real test is,

R = double.empty(1,0);
R.*R

ans =

  1×0 empty double row vector

sum(R)

ans = 0

[Paul]

"The Horner loop naturally produces zero as a result for empty polynomials."

As @dpb showed the output of polyval with empty coefficients is not the natural output of the Horner loop, so someone at sometime made a conscious decision as to how polyval should treat this specific case.

[Steven Lord]

Given that polyval probably goes back to version 1 of MATLAB as written roughly in 1984,

polyval was in listed in the MATLAB 1.3 function list quoted in this post on Cleve's blog. I wouldn't be surprised if it was in version 1.0 as well. But it wasn't in Cleve's original "Historic MATLAB" user guide; its name had too many letters for that :)