Opened 10 years ago

Closed 10 years ago

#11356 closed enhancement (fixed)

Companion matrix constructor

Reported by: rbeezer Owned by: jason, was
Priority: minor Milestone: sage-4.7.2
Component: linear algebra Keywords: beginner, sd31
Cc: fidelbarrera Merged in: sage-4.7.2.alpha1
Authors: Rob Beezer Reviewers: David Loeffler
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by rbeezer)

This will be used to construct the output of an upcoming rational canonical form.

Apply:

  1. trac_11356-companion-matrix-v4.patch

Attachments (4)

trac_11356-companion-matrix.patch (7.7 KB) - added by rbeezer 10 years ago.
trac_11356-companion-matrix-v2.patch (7.7 KB) - added by rbeezer 10 years ago.
trac_11356-companion-matrix-v3.patch (8.1 KB) - added by rbeezer 10 years ago.
trac_11356-companion-matrix-v4.patch (8.4 KB) - added by rbeezer 10 years ago.

Download all attachments as: .zip

Change History (23)

Changed 10 years ago by rbeezer

comment:1 Changed 10 years ago by rbeezer

  • Authors set to Rob Beezer
  • Cc fidelbarrera added
  • Description modified (diff)
  • Keywords beginner added
  • Status changed from new to needs_review

comment:2 follow-up: Changed 10 years ago by jason

Note that Magma defaults to format='bottom', I think. Is there any consistency issues with us defaulting to format='right', given that we follow the Magma convention of row vectors?

comment:4 in reply to: ↑ 2 ; follow-up: Changed 10 years ago by rbeezer

Replying to jason:

Note that Magma defaults to format='bottom', I think. Is there any consistency issues with us defaulting to format='right', given that we follow the Magma convention of row vectors?

Everything I read about companion matrices and rational canonical form (Frobenius form) uses the "right" version. It is the natural thing to use when you put your basis vectors into a matrix as columns, as is done with QR, Jordan form, and maybe others.

So I think "right" is the right default (pun intended), but "bottom" (and "top" and "left") are available for folks constructing less natural objects.

comment:5 in reply to: ↑ 4 ; follow-up: Changed 10 years ago by jason

Replying to rbeezer:

Replying to jason:

Note that Magma defaults to format='bottom', I think. Is there any consistency issues with us defaulting to format='right', given that we follow the Magma convention of row vectors?

Everything I read about companion matrices and rational canonical form (Frobenius form) uses the "right" version. It is the natural thing to use when you put your basis vectors into a matrix as columns, as is done with QR, Jordan form, and maybe others.

Yes, and my point is that since we follow the magma convention of putting basis vectors in rows, do we need to be consistent with their convention of format='bottom'? And yes, I've also always seen it with format='right' as well.

comment:6 in reply to: ↑ 5 Changed 10 years ago by rbeezer

Replying to jason:

Yes, and my point is that since we follow the magma convention of putting basis vectors in rows, do we need to be consistent with their convention of format='bottom'? And yes, I've also always seen it with format='right' as well.

And my point is that "follow the convention" is stronger than the reality. I like to say Sage has a "preference" for rows. The RDF/CDF decompositions return basis vectors in columns, Jordan form returns basis vectors in columns and I'm sure I can find more. So, if I can get a basis to convert to rational canonical form, then "right" will be the correct choice. I think this is a place where consistency for other decompositions is to be preferred.

Besides the overwhelming use of "right" in the literature. I would rather not look oddball to newcomers, just to be consistent with a language with a miniscule audience.

Rob

Changed 10 years ago by rbeezer

comment:7 Changed 10 years ago by rbeezer

  • Description modified (diff)

This needed rebasing, which is now the v2 patch.

comment:8 follow-ups: Changed 10 years ago by ddrake

Perhaps you should add a little suggestion for converting a symbolic polynomial to the kind of list this function needs; something like:

sage: x = var('x'); sympoly = x^3 + 2*x + 5
sage: parent(sympoly)
Symbolic Ring
sage: coefflist = [sympoly(x=0)] + [sympoly.coeff(x^k) for k in [1..sympoly.degree(x)]]; coefflist
[5, 2, 0, 1]
sage: companion_matrix(coefflist)
...whatever...

(One might be tempted to use .coeffs(x), but that leaves out zero coefficients.)

comment:9 in reply to: ↑ 8 Changed 10 years ago by rbeezer

Replying to ddrake:

Perhaps you should add a little suggestion for converting a symbolic polynomial to the kind of list this function needs; something like:

Excellent idea.

comment:10 in reply to: ↑ 8 ; follow-up: Changed 10 years ago by rbeezer

  • Description modified (diff)
  • Keywords sd31 added

Replying to ddrake:

Perhaps you should add a little suggestion for converting a symbolic polynomial to the kind of list this function needs; something like:

Doctest section about symbolic polynomials has been expanded to reflect Dan's suggestion, and incorporated into a standalone v3 patch. Thanks for the suggestion, Dan.

comment:11 in reply to: ↑ 10 ; follow-up: Changed 10 years ago by ddrake

Replying to rbeezer:

Doctest section about symbolic polynomials has been expanded to reflect Dan's suggestion, and incorporated into a standalone v3 patch. Thanks for the suggestion, Dan.

Uh oh, your v2 and v3 patches seem identical...

Changed 10 years ago by rbeezer

comment:12 in reply to: ↑ 11 Changed 10 years ago by rbeezer

Replying to ddrake:

Uh oh, your v2 and v3 patches seem identical...

Must've forgotten an hg qrefresh. Sorry for the hassle.

Replaced the v3 patch with one that should be different than v2. Thanks for the catch.

comment:13 follow-up: Changed 10 years ago by ddrake

  • Status changed from needs_review to needs_work

If you feed companion_matrix the empty list, it complains about an IndexError. I'd rather see it:

  • return the empty matrix, or
  • change line 2839 to if n == 0 or or not poly[n] == 1: so that the ValueError actually gets raised.

Returning the empty matrix seems about right, but I can imagine people having strong opinions about the zero polynomial not being monic. I don't know about the conventions in this corner case, so do whatever seems best.

Changed 10 years ago by rbeezer

comment:14 in reply to: ↑ 13 Changed 10 years ago by rbeezer

  • Description modified (diff)

Replying to ddrake:

Thanks, Dan.

Seems like an input list of [1] should be a monic polynomial that creates an empty matrix. Code does that before latest patch and a test of this has been added in the v4 patch.

So I made an input empty list fail in the v4 patch and added a test. In this case, n = -1, so various existing array references will fail, thus requiring its own error message. I tried to build an "empty polynomial" from an empty list, but just got the zero polynomial. So I think an empty list is the only danger, thus the error message reads this way.

comment:15 Changed 10 years ago by rbeezer

  • Status changed from needs_work to needs_review

Forgot to set this as "needs review" when I put up the v4 patch.

comment:16 follow-up: Changed 10 years ago by davidloeffler

  • Status changed from needs_review to positive_review

This looks great -- code is very clear and thorough with full documentation and tests, all of which pass. Positive review.

comment:17 in reply to: ↑ 16 Changed 10 years ago by rbeezer

Replying to davidloeffler:

Thanks, David, for taking the time to look at this. -Rob

comment:18 Changed 10 years ago by jdemeyer

  • Milestone changed from sage-4.7.1 to sage-4.7.2
  • Reviewers set to David Loeffler

comment:19 Changed 10 years ago by jdemeyer

  • Merged in set to sage-4.7.2.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.