Opened 7 years ago

Closed 6 years ago

#13393 closed defect (fixed)

Vector normalization

Reported by: chrisjamesberg Owned by: Chris Berg
Priority: major Milestone: sage-5.7
Component: linear algebra Keywords: vector, normalize
Cc: jason, saliola, novoselt, rbeezer, serrano, gagern Merged in: sage-5.7.beta0
Authors: Chris Berg, Eviatar Bach Reviewers: Luis Serrano, Benjamin Jones
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

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

Attachments (2)

combined.patch (3.1 KB) - added by eviatarbach 6 years ago.
trac_13393_reviewer.patch (796 bytes) - added by benjaminfjones 6 years ago.
reviewer patch

Download all attachments as: .zip

Change History (42)

comment:1 Changed 7 years ago by jason

  • Cc jason added

comment:2 Changed 7 years ago by chrisjamesberg

  • Status changed from new to needs_review

comment:3 Changed 7 years ago by chrisjamesberg

  • Cc saliola added

comment:4 Changed 7 years ago by novoselt

  • Cc novoselt added

comment:5 Changed 7 years ago by 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?

comment:6 Changed 7 years ago by chrisjamesberg

  • Status changed from needs_review to needs_work

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.

comment:7 Changed 7 years ago by 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.)

comment:8 Changed 7 years ago by 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.

comment:9 Changed 7 years ago by jason

  • Cc rbeezer added

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

comment:10 follow-up: Changed 7 years ago by 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.

comment:11 follow-up: Changed 7 years ago by kcrisman

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

comment:12 in reply to: ↑ 11 ; follow-up: Changed 7 years ago by 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.

comment:13 Changed 7 years ago by jason

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

comment:14 in reply to: ↑ 10 Changed 7 years ago by 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.

comment:15 Changed 7 years ago by 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.

comment:16 in reply to: ↑ 12 Changed 7 years ago by 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...

comment:17 Changed 6 years ago by chrisjamesberg

Patchbot!

Apply:trac_13393_vector_normalization_cb.patch

comment:18 Changed 6 years ago by chrisjamesberg

  • Cc serrano added
  • Reviewers set to Luis Serrano
  • Status changed from needs_work to needs_review

comment:19 Changed 6 years ago by jason

  • Status changed from needs_review to needs_work

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()

comment:20 Changed 6 years ago by gagern

  • Cc gagern added

comment:21 Changed 6 years ago by eviatarbach

  • Status changed from needs_work to needs_review

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).

comment:22 Changed 6 years ago by benjaminfjones

  • Reviewers changed from Luis Serrano to Luis Serrano, Benjamin Jones

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:

comment:23 Changed 6 years ago by eviatarbach

  • Authors changed from Chris Berg to Chris Berg, Eviatar Bach

comment:24 Changed 6 years ago by 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

comment:25 Changed 6 years ago by benjaminfjones

  • Status changed from needs_review to needs_work
  • Work issues set to doctest, docstring

@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.

comment:26 Changed 6 years ago by eviatarbach

  • Status changed from needs_work to needs_review

Ah, yes. Hope another cumulative patch is okay.

comment:27 Changed 6 years ago by 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).

comment:28 Changed 6 years ago by eviatarbach

  • Description modified (diff)

Thanks :)

Patchbot: apply combined.patch

Changed 6 years ago by eviatarbach

comment:29 Changed 6 years ago by ppurka

Patchbot apply combined.patch

comment:30 Changed 6 years ago by benjaminfjones

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

comment:31 Changed 6 years ago by benjaminfjones

  • Status changed from needs_review to positive_review

All doctests pass.

comment:32 Changed 6 years ago by jdemeyer

  • Work issues doctest, docstring deleted

comment:33 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work
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
**********************************************************************

comment:34 Changed 6 years ago by jdemeyer

* ping *

comment:35 Changed 6 years ago by benjaminfjones

I'll provide a reviewer patch for this.

Changed 6 years ago by benjaminfjones

reviewer patch

comment:36 Changed 6 years ago by benjaminfjones

  • Status changed from needs_work to needs_review

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

Patchbot, apply combined.patch trac_13393_reviewer.patch

comment:37 Changed 6 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:38 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.6 to sage-5.7

comment:39 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:40 Changed 6 years ago by jdemeyer

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