[sage-algebra] Coercion for free modules

[Simon King]

Hi!

I hope that one of the 13 group members reads this...

I noticed the following:

sage: P.<t> = ZZ[]
sage: M1 = FreeModule(P,3)
sage: M2 = QQ^3
sage: M2([1,1/2,1/3]) + M1([t,t^2+t,3]) # This is ok
(t + 1, t^2 + t + 1/2, 10/3)
sage: M3 = FreeModule(P,3, inner_product_matrix = Matrix(3,3,range(9)))
sage: M2([1,1/2,1/3]) + M3([t,t^2+t,3]) # This should result in an error
(t + 1, t^2 + t + 1/2, 10/3)

Why do I think that an error should result?
I believe that the inner product is an important aspect of the
structure. Since M2 and M3 have different inner product matrix, there
must be no coercion IMO. I mean, what inner product should the parent
of M2([1,1/2,1/3]) + M3([t,t^2+t,3]) have?

I know what I have to change (namely the merge method of VectorFunctor),
but I first want to ask whether other people agree that M2([1,1/2,1/3])
+ M3([t,t^2+t,3]) should result in an error.

Best regards,
Simon

[John Cremona]

I read it :)

I haven't ever used FreeModules with inner product. What seems to be
happening is just that the inner product is ignored in forming the
sum. That seems dangerous, and I would be happier if the user had to
do an explicit coercion for this.

John

[William Stein]

On Mon, May 17, 2010 at 7:20 AM, Simon King <simon...@nuigalway.ie> wrote:
> Hi!
>
> I hope that one of the 13 group members reads this...

I read it too.

I think much better and natural is that the sum would be an element of
FreeModule(QQ[t],3), i.e., without the inner product. After all, the
user is explicitly writing that they want to sum those two objects.
If there is a reasonable and unambiguous way to do it, why not allow
it?

This is similar in my mind to typing "1/2 + x" where 1/2 in QQ and x
in ZZ['x']. In both cases there is a natural map to QQ[x].
Similarly, here there is a natural map to FreeModule(QQ[t],3). I
view "forget the inner product" as a natural map.

Note that what I am suggesting *is* what Sage currently does.

So I'm -1 to your suggested change.

- William



--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org

[Simon King]

Hi!

I see that John Cremona has answered to my question, but I am afraid
that, when I see the message in my browser, I can not see a "reply"
button nor a "new post" button. How does that come?

Anyway, John, I understand your reply that you would agree that a
coercion error would make sense in the given setting?

Cheers,
Simon

[Simon King]

Hi again!

OK, William is -1 to this change.

I agree that the map you describe is natural. But I thought that a
coercion has to be a *structure* preserving map -- and I thought that
the inner product is important for the structure.

But of course I acknowledge that the current setting is consistent: In
my example, M1 and M2 evaluate as equal, although they have different
inner products, and thus it is consequent to allow coercion.

So, I leave it as it is...

Cheers,
Simon

[William Stein]

On Mon, May 17, 2010 at 8:31 AM, Simon King <simon...@nuigalway.ie> wrote:
> Hi again!
>
> OK, William is -1 to this change.
>
> I agree that the map you describe is natural. But I thought that a
> coercion has to be a *structure* preserving map -- and I thought that
> the inner product is important for the structure.

You're right -- it would be much better if the free module that the
sum lives in didn't
have any inner product at all, instead of having the trivial one.

> But of course I acknowledge that the current setting is consistent: In
> my example, M1 and M2 evaluate as equal, although they have different
> inner products, and thus it is consequent to allow coercion.
>
> So, I leave it as it is...

Another possibility would be a setting for the inner product to "None"
or something like that.

Then the map preserves structure in that it is just forgetful.

[Simon King]

Sorry, I still don't see a way to properly reply to posts, as the web
browser interface doesn't provide it (although it works fine for
sage-devel and sage-support).

What about the following approach:

* The (current and future) standard inner product is given by the
unit matrix
* If one of the summands has a standard inner product then the sum
inherits the inner product of the other summand.
* If both summands have a non-standard inner product then
apparently the user cares about the inner product. Thus coercion
should respect this structure. I.e., both summands must have the
same inner product matrix, or a coercion error results.

This would yield consistency for those who care about the inner product,
and "user friendliness" for those who are happy with the standard inner
product.

Cheers,
Simon

[William Stein]

What if the user specifically requests the identity matrix inner
product? Then they care about it.
I think we need a "None" inner product.

-- William

[John Cremona]

We need a None inner product unless there is a separate class for
vector space, and inner product space. However, I can imagine users
who will want the standard inner product available for any vector
space without necessarily constructing an inner product space as such.
So, when a v.s. is constructed should it get None as the default i.p.
or the standard i.p.?

John

PS Simon, can you set your settings for this list to be to send you
emails? That is what I do, so I can reply using email.

[Simon King]

Hi!

I think this is already implemented, and easily available by duck
typing.

Namely, the free module has an attribute _inner_product_matrix *if and
only if* the user requests it. This is even the case when the user
requests the default product.

So, I guess that's the way to go: Test the presence of the attribute,
and take care of it if it exists.

Cheers,
Simon

[William Stein]

That sounds reasonable. It might be nicer to abstract this out a
little with a function though... (i.e., instead of checking for hidden
attributes).

>
> Cheers,
> Simon

[Simon King]

For your information.

If there is no veto, my patch for ticket #8972 will provide:

Two modules without explicitly given inner product allow coercion::

sage: M1 = QQ^3

sage: P.<t> = ZZ[]

sage: M2 = FreeModule(P,3)
sage: M1([1,1/2,1/3]) + M2([t,t^2+t,3]) # indirect doctest

(t + 1, t^2 + t + 1/2, 10/3)

If only one summand has an explicit inner product, the result will be
provided
with it::

sage: M3 = FreeModule(P,3, inner_product_matrix =
Matrix(3,3,range(9)))

sage: M1([1,1/2,1/3]) + M3([t,t^2+t,3])

(t + 1, t^2 + t + 1/2, 10/3)

sage: (M1([1,1/2,1/3]) + M3([t,t^2
+t,3])).parent().inner_product_matrix()
[0 1 2]
[3 4 5]
[6 7 8]

If both summands have an explicit inner product (even if it is the
standard
inner product), then the products must coincide. The only difference
between
``M1`` and ``M4`` in the following example is the fact that the default
inner product was *explicitly* requested for ``M4``. It is therefore not
possible to coerce with a different inner product::

sage: M4 = FreeModule(QQ,3, inner_product_matrix = Matrix(3,3,1))
sage: M4 == M1
True
sage: M4.inner_product_matrix() == M1.inner_product_matrix()
True
sage: M4([1,1/2,1/3]) + M3([t,t^2+t,3]) # indirect doctest
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for '+': 'Ambient quadratic
space of dimension 3 over Rational Field
Inner product matrix:
[1 0 0]
[0 1 0]
[0 0 1]' and 'Ambient free quadratic module of rank 3 over the
integral domain Univariate Polynomial Ring in t over Integer Ring
Inner product matrix:
[0 1 2]
[3 4 5]
[6 7 8]'


Thanks for your feedback!
Simon

[Simon King]

Hi William,

I think relying on the existence of a hidden attribute is fine in this
case. Namely, the only place where one needs it is in the construction()
method of the module: It returns a VectorFunctor, and this construction
functor is equipped with the inner product matrix (which can be None).

The rest of the implementation happens inside the merge() method of
VectorFunctor.

Cheers,
Simon

[David R. Kohel]

Hi Simon,

I also agree that the sum should give an coercion error, and that
a None inner product matrix should exist. One should verify that
it doesn't get redefined to the identity matrix by a call to
inner_product_matrix.

Once an non-default inner product has been specified, this data
should be preserved by the coercion machinery. The specification
of an inner product should be viewed as a user-defined change of
default category to that of modules with inner product.

From the examples you give, your patch maintains this distinction.

It is a tempting approach to apply a forgetful functor as coercion
when such exists, but your bug report illustrates that this is not
a good idea (here specifically, and maybe in general).

Cheers,

David

[William Stein]

Since I came to exactly the opposite conclusion, could you further
explain why you think his bug report illustrates that applying the
forgetful functor is not a good idea?

-- William

[King, Simon]

Hi!

I tried to send this a couple of minutes ago, but it seems that it didn't arrive.

This is supposed to be a comment on William's question on David's remark that my example shows that it is not always a good idea to use a forgetful functor (if it exists) for coercion.

David wrote:
> It is a tempting approach to apply a forgetful functor as coercion
> when such exists, but your bug report illustrates that this is not
> a good idea (here specifically, and maybe in general).

He does not say that a forgetful coercion is *always* a bad idea. But there *are* situations in which it is bad, and therefore it is not good to allow forgetful coercion *whenever it exists*.

E.g., it is easy to imagine applications where it is essential that one has a unit vector (norm one). Using a forgetful coercion in the setting of my example, a unit vector would be coerced into something completely different, without Sage complaining.

Another example: For many people, the term order of a polynomial ring doesn't matter. But I often work with Gröbner bases, and so I don't like when there is a coercion between polynomial rings of different term orders. Perhaps it would be too much to call this a bug (and I *don't* suggest it should change: The majority of users really couldn't care less), but at least it encourages the user to produce incorrect code.

Or, perhaps a killer example: Forgetting the multiplicative structure of MatrixSpace(QQ,2,2) would in fact yield QQ^4. But would you really like to call this forgetful functor a coercion? Would you really like that MatrixSpace(QQ,2,2)([1,2,3,4])+(QQ^4)([1,2,3,4])==(QQ^4)([2,4,6,8]) ??

I understand the comments in this thread like this and will try to take care of it in my patch:
1. We agree that coercion must preserve all "important" algebraic structures.
2. Which structures are important depends on the context and on the aim of the user.
3. If the user explicitly defines a structure, then it is reasonable to assume that this structure is important (here, the inner product) -- hence, in this case, a forgetful functor is not so good.

Cheers,
Simon

[Nicolas M. Thiery]

On Mon, May 17, 2010 at 10:21:48PM +0100, King, Simon wrote:
> This is supposed to be a comment on William's question on David's
> remark that my example shows that it is not always a good idea to
> use a forgetful functor (if it exists) for coercion.
>
> David wrote:
> > It is a tempting approach to apply a forgetful functor as coercion
> > when such exists, but your bug report illustrates that this is not
> > a good idea (here specifically, and maybe in general).
>
> He does not say that a forgetful coercion is *always* a bad idea. But there *are* situations in which it is bad, and therefore it is not good to allow forgetful coercion *whenever it exists*.
>
> E.g., it is easy to imagine applications where it is essential that one has a unit vector (norm one). Using a forgetful coercion in the setting of my example, a unit vector would be coerced into something completely different, without Sage complaining.
>

> Another example: For many people, the term order of a polynomial ring doesn't matter. But I often work with Gr�bner bases, and so I don't like when there is a coercion between polynomial rings of different term orders. Perhaps it would be too much to call this a bug (and I *don't* suggest it should change: The majority of users really couldn't care less), but at least it encourages the user to produce incorrect code.

>
> Or, perhaps a killer example: Forgetting the multiplicative structure of MatrixSpace(QQ,2,2) would in fact yield QQ^4. But would you really like to call this forgetful functor a coercion? Would you really like that MatrixSpace(QQ,2,2)([1,2,3,4])+(QQ^4)([1,2,3,4])==(QQ^4)([2,4,6,8]) ??
>
> I understand the comments in this thread like this and will try to take care of it in my patch:
> 1. We agree that coercion must preserve all "important" algebraic structures.
> 2. Which structures are important depends on the context and on the aim of the user.
> 3. If the user explicitly defines a structure, then it is reasonable to assume that this structure is important (here, the inner product) -- hence, in this case, a forgetful functor is not so good.

My 2 cents on this debate: I agree that applying forgetful functors
automatically can come in handy in interactive use. However, from my
experience:

- In code, one rarely cares about such coercions; on the other hand,
having them can prevent catching errors early-on, and letting them
propagate far far away where they get hard to debug.

- Coercion ought to be predictable, consistent, robust, and fast. Oh,
and easy to refactor as well. To this end, the coercion model has
to be as simple and centralized as possible. Handling special cases
all over the places in Sage is just looking for trouble.

- It is hard to disable an existing coercion if at some point in time
it is deemed as too dangerous.

- In short, explicit is better than implicit here.

I hence vote for being very very conservative when adding new
coercions. And when this is done, this should be implemented as much
as possible as a general rule.

Best,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[King, Simon]

Hi Nicolas!

> - Coercion ought to be predictable, consistent, robust, and fast. Oh,
> and easy to refactor as well. To this end, the coercion model has
> to be as simple and centralized as possible. Handling special cases
> all over the places in Sage is just looking for trouble.

I think it is rather centralised in Sage! There is just *one* file (namely pushout.py) where all the construction functors live:

Each construction functor a rank, defining the precedence of the functor; the "merge()" method allows to fuse different functors of the same rank into one (typically taking care of different implementations of the same mathematical construction); and the "commutes()" method provides more freedom by stating that certain functors of the same rank commute. And then of course there is a call method for objects and (once #8807 gets a positive review, hint, hint) for morphisms.

If one has two functors F1, F2 of the same rank and wants to disallow a pushout of F1(R) and F2(R) (where R is some object), then essentially one has to make sure that F1.merge(F2) and F2.merge(F1) both return None. In my example, F1 and F2 are VectorFunctors with and without inner product matrix. This all happens in one place, pushout.py!

The only non-centralised aspect is that most parent structures should have a "construction()" method that is not simply returning None. This is, unfortunately, not the case for LaurentSeriesRing -- should be implemented.

> - It is hard to disable an existing coercion if at some point in time
> it is deemed as too dangerous.

No. My suggestion for free modules with and without inner product is in fact about disabling an existing coercion: Note that, at present, coercion is enabled regardless of the inner product structure, and I suggest to be more restrictive (IF the user provides an inner product).

And it is really not difficult to disable it: Two lines in the "constuction()" method of the free modules, and few lines in the "merge()" method of the construction functor.

> - In short, explicit is better than implicit here.

Does this mean "if a structure is explicit then it should be preserved"?

> I hence vote for being very very conservative when adding new
> coercions. And when this is done, this should be implemented as much
> as possible as a general rule.

As I said, this is not about adding but about removing a coercion.

Best regards,
Simon

[David R. Kohel]

Hi,

I don't have a better response, in the sense that I concur that important
structures should not vanish by means of binary operations (+, *, etc.)
with objects that don't carry this structure, but don't have a general rule,
or categorical justification, at the moment.

It is true that there is a forgetful functor from quadratic modules to the
underlying modules, so I could see an argument for applying the forgetful
functor. On the other hand, if the inner product structure is lost due
to mistaken combination with a vector in another space, it could be hard
to trace and debug where this has occurred.

Term orders on polynomial rings are somewhat different, in that the choice
of term order don't change the morphisms. On the other hand, exactly as
for the choice of inner product on a quadratic module, the fact that two
term orders are chosen (by a user) to be different suggests that these
structures are not intended to be canonically identified.

There is some standard in Sage for differentiating structures for which
a user has specified different generator names. Not applying an automatic
coercion-by-forgetul-functor seems more in the spirit of this -- respecting
the user's choice.

Cheers,

David

[Nicolas M. Thiery]

Hi Simon!

On Mon, May 17, 2010 at 11:41:52PM +0100, King, Simon wrote:
> No. My suggestion for free modules with and without inner product is
> in fact about disabling an existing coercion: Note that, at present,
> coercion is enabled regardless of the inner product structure, and I
> suggest to be more restrictive (IF the user provides an inner
> product).

I know: I am precisely pushing in this direction :-)

The rule of thumb you found sounds reasonable (though if it was just
for me, I would simply drop any coercion between to non identical free
modules).

> > - Coercion ought to be predictable, consistent, robust, and fast. Oh,
> > and easy to refactor as well. To this end, the coercion model has
> > to be as simple and centralized as possible. Handling special cases
> > all over the places in Sage is just looking for trouble.
>
> I think it is rather centralised in Sage! There is just *one* file
> (namely pushout.py) where all the construction functors live:

Yes, it's quite good indeed! But there is still quite some dispersed
coercion logic (mostly in remaining __call__, and some too-complicated
coerce_map_from methods). I am currently working on improving the
coercion lookup (#8878), and the later are really a pain to handle.

> > - It is hard to disable an existing coercion if at some point in time
> > it is deemed as too dangerous.

> And it is really not difficult to disable it: Two lines in the
> "constuction()" method of the free modules, and few lines in the
> "merge()" method of the construction functor.

I meant that it can be hard from a backward compatibility point of
view when users got used to a given coercion.

> > - In short, explicit is better than implicit here.
>
> Does this mean "if a structure is explicit then it should be preserved"?

I just meant that, in case of doubt, I prefer not to have a coercion,
even if I have to pay the price of having to be more explicit.

Cheers,

[William Stein]

On Mon, May 17, 2010 at 3:56 PM, Nicolas M. Thiery
<Nicolas...@u-psud.fr> wrote:
>        Hi Simon!
>
> On Mon, May 17, 2010 at 11:41:52PM +0100, King, Simon wrote:
>> No. My suggestion for free modules with and without inner product is
>> in fact about disabling an existing coercion: Note that, at present,
>> coercion is enabled regardless of the inner product structure, and I
>> suggest to be more restrictive (IF the user provides an inner
>> product).
>
> I know: I am precisely pushing in this direction :-)
>
> The rule of thumb you found sounds reasonable (though if it was just
> for me, I would simply drop any coercion between to non identical free
> modules).

Really? I can think of many situations where I disagree with doing
so. E.g., what
if you have two submodules A,B of QQ^n and elements x in A and y in B, and write
x + y
Do you really want that to fail?

Or, suppose that W is a subspace of V and one forms V/W, which is
itself a free module (over a field). Shouldn't there be a canonical
coercion from V to V/W?

Also, what about R^n (or any submodule of it) having a canonical map
into Frac(R)^n?

William