Vector normalization

[chrisjamesberg]

Fix vector normalization so that it agrees with the standard definition of normalizing a vector. Right now it divides the entries of the vector by the first nonzero entry of the vector. For instance:

sage: v = vector([1,2,3])

sage: v.normalize()

(1, 2, 3)

Shouldn't the default implementation be the Euclidean norm? Especially since v.norm() returns the Euclidean norm.

---

Apply combined.patch​ and trac_13393_reviewer.patch​

[kcrisman]

Hmm, would this need deprecation? (Though I totally agree that this is the 'usual' definition.) I wonder what the original author of this was thinking ... maybe there is a use case in which this is a very natural thing to do?

[chrisjamesberg]

I assume it would. I put this patch up in hopes that the patchbot would show me where it needs deprecation. Perhaps putting it to needs review was premature, I was just trying to get the patchbot to run, and didn't realize someone would respond so quickly. Changing back to needs work.

I can't see how dividing by the first part is more natural than dividing by the norm.

[novoselt]

I think I've seen such a normalization in projective spaces code. But it seems that the point there was to get a concrete representative for a projective point - making the first non-zero to be one worked. (I am not sure if it is still used somewhere, Volker has rewritten a lot of schemes code.)

[jason]

Personally, I think someone ought to ping sage-devel about this change. The "standard definition" may be different in number theory or other fields, for example.

[jason]

CCing rbeezer, since he likely already advocated for this change... :)

[rbeezer]

What if your base ring/field does not have any square roots?

sage: v = vector([1,2,3])
sage: n = v.norm()
sage: n
sqrt(14)
sage: u = (1/n)*v
sage: u.base_ring()
Symbolic Ring

We start with a free module element (integer entries) and then we end up in the Symbolic Ring (which is often hard to get out of).

Over RDF/CDF I'd agree entirely. For exact linear algebra, I'm not convinced.

[kcrisman]

Hmm, but in that case what does normalization even mean? Then we should just get rid of this function entirely.

[novoselt]

Replying to kcrisman:

Hmm, but in that case what does normalization even mean? Then we should just get rid of this function entirely.

If you think of vectors as specifying directions, then normalization gives you a "random but fixed" vector pointing in the same direction as the original. If you store a lot of directions, then comparing normalized vectors is quicker than using dot-products.

[jason]

I've also used this normalization when dealing with projective spaces, like mentioned in one of the comments above.

[chrisjamesberg]

If you want to go that route, I could argue, what if your ring doesn't have division...

I'm sure you have a good point, and I'm not as Sage savvy as most users here, but from my perspective someone who is trying to use Sage for basic functionality (like an undergrad trying to do homework) will be really confused and frustrated if v.normalize() does not return a normalized vector. In fact, this was how it was pointed out to me. I'm sure other mathematicians use the functionality of what v.normalize() was doing before, but these people are smart enough to write their own such code. Or if it really is important it should be there, but shouldn't be called normalize.

Replying to rbeezer:

What if your base ring/field does not have any square roots?

sage: v = vector([1,2,3])
sage: n = v.norm()
sage: n
sqrt(14)
sage: u = (1/n)*v
sage: u.base_ring()
Symbolic Ring

We start with a free module element (integer entries) and then we end up in the Symbolic Ring (which is often hard to get out of).

Over RDF/CDF I'd agree entirely. For exact linear algebra, I'm not convinced.

[jason]

I personally think normalize should be what Chris says, but we have to take into account backwards compatibility and people that may have code that depends on the current functionality. The way to resolve this design decision is to take a vote on sage-devel. Chris, can you post there, explain what is done now and what you'd like to change it to (maybe give an example and link to this ticket), and call for a vote for the design change?

I personally will vote +1 for this change.

[kcrisman]

Hmm, but in that case what does normalization even mean? Then we should just get rid of this function entirely.

If you think of vectors as specifying directions, then normalization gives you a "random but fixed" vector pointing in the same direction as the original. If you store a lot of directions, then comparing normalized vectors is quicker than using dot-products.

My point was that if there isn't a consistent way to do it that makes everybody happy... At the least, can we find another name for the current function when you make that vote on sage-devel? Someone will presumably need it...

[chrisjamesberg]

Patchbot!

Apply:trac_13393_vector_normalization_cb.patch

[jason]

Whatever happened to the consensus from sage-devel?

​https://groups.google.com/forum/?fromgroups=#!topic/sage-devel/p5ZfTfgBIAs

• deprecate normalize() and point to normalized() and normal_form()
• normalized() is division by L2-norm
• normal_form() is the old normalize()

[eviatarbach]

How does this patch look? I added normalized() for p-norm, deprecated normalize(), and renamed it to monic() (couldn't get too much consensus on sage-devel, but that seemed to be the most popular option).

[benjaminfjones]

Looks good to me. I'll wait for patchbot and other folks to chime in if they desire before giving a positive review.

Patchbot, please, if you would, apply:

• trac_13393_normalized.patch
• trac_13393_normalized_2.patch

[ppurka]

@benjaminfjones - here's the proper syntax for patchbot - no links, everything in one line and in the order in which to apply. What is really important is the apply part. The patchbot part is not necessary, but it is useful to tell us poor humans that we are not addressing someone else ;)

Patchbot: apply trac_13393_normalized.patch trac_13393_normalized_2.patch

[benjaminfjones]

@ppurka - Thanks. I feel stupid for not knowing this by now :)

@eviatarbach - It looks like the normalize() needs a docstring and doctest. One doctest that covers the deprecation exception should do it.

[eviatarbach]

Ah, yes. Hope another cumulative patch is okay.

[ppurka]

I think these are all small changes, and so you can merge them all into one file - the first patch. You can do the merge using ​mercurial itself. You will need to do the following - for details see the wiki I linked to. I will assume that you have your three patches in your queue and are unapplied.

...6.beta0/devel/sage [255] » hg qser  # <<< how it looks now
trac13032_doc.patch                # <<< blue color, already applied
trac_10508_doctest.patch           # <<< blue color, already applied
trac_10508_update_atlas_docs.patch # <<< blue color, already applied
new.patch                          # <<< grey color, unapplied patch
trac_13393_normalized_2.patch      # <<< grey color, unapplied patch
trac_13393_normalized.patch        # <<< grey color, unapplied patch

...sage-5.6.beta0/devel/sage» hg qpush --move trac_13393_normalized.patch
applying trac_13393_normalized.patch
now at: trac_13393_normalized.patch

...sage-5.6.beta0/devel/sage» hg qfold trac_13393_normalized_2.patch
...sage-5.6.beta0/devel/sage» hg qfold new.patch

...sage-5.6.beta0/devel/sage» hg export tip | head  # <<<< Notice the merged commit messages.
# HG changeset patch
# User Eviatar Bach <snip>
# Date 1356146661 28800
# Node ID 110394caabbfb0cc7dd9f81ce865f68bdb9c17b9
# Parent  d6de0068244b5820661ab3bde2082862a53bf536
Trac 13393: new 'normalized' method for vectors, deprecating 'normalize'
* * *
Trac 13393: proper deprecation
* * *
Trac 13393: Docstring and doctest for .normalize()

...sage-5.6.beta0/devel/sage» hg qser  # <<< How the queue looks after the merge
trac13032_doc.patch
trac_10508_doctest.patch
trac_10508_update_atlas_docs.patch
trac_13393_normalized.patch

Once you are done you can upload the merged patch, give the correct 'apply' command to the patchbot, and modify the description of this ticket to let others know which patch to apply (otherwise one has to read through all of the comments to figure it out).

[eviatarbach]

Thanks :)

Patchbot: apply combined.patch

[ppurka]

Patchbot apply combined.patch

[benjaminfjones]

Looks good, thanks! Waiting on doctests to finish..

[benjaminfjones]

All doctests pass.

[jdemeyer]

sage -t  -force_lib devel/sage/sage/modules/finite_submodule_iter.pyx
**********************************************************************
File "/release/merger/sage-5.6.beta2/devel/sage-main/sage/modules/finite_submodule_iter.pyx", line 314:
    sage: all([ x.normalize() == x for x in FiniteFieldsubspace_projPoint_iterator(A, True) ])
Expected:
    True
Got:
    doctest:1172: DeprecationWarning: 'normalize' is deprecated. For division by the p-norm use 'normalized', and for division by the firs
t nonzero entry use 'monic'.
    See http://trac.sagemath.org/13393 for details.
    True
**********************************************************************

[jdemeyer]

* ping *

[benjaminfjones]

I'll provide a reviewer patch for this.

[benjaminfjones]

reviewer patch

[benjaminfjones]

Reviewer patch addresses the work issues. @jdemeyer, do you mind reviewing the reviewer patch?

Patchbot, apply combined.patch trac_13393_reviewer.patch