Opened 9 years ago
Closed 8 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 )
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)
Change History (42)
comment:1 Changed 9 years ago by
- Cc jason added
comment:2 Changed 9 years ago by
- Status changed from new to needs_review
comment:3 Changed 9 years ago by
- Cc saliola added
comment:4 Changed 9 years ago by
- Cc novoselt added
comment:5 Changed 9 years ago by
comment:6 Changed 9 years ago by
- 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 9 years ago by
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 9 years ago by
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 9 years ago by
- Cc rbeezer added
CCing rbeezer, since he likely already advocated for this change... :)
comment:10 follow-up: ↓ 14 Changed 9 years ago by
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: ↓ 12 Changed 9 years ago by
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: ↓ 16 Changed 9 years ago by
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 9 years ago by
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 9 years ago by
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 RingWe 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 9 years ago by
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 9 years ago by
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 9 years ago by
Patchbot!
Apply:trac_13393_vector_normalization_cb.patch
comment:18 Changed 9 years ago by
- Cc serrano added
- Reviewers set to Luis Serrano
- Status changed from needs_work to needs_review
comment:19 Changed 9 years ago by
- 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 9 years ago by
- Cc gagern added
comment:21 Changed 8 years ago by
- 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 8 years ago by
- 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 8 years ago by
comment:24 Changed 8 years ago by
@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 8 years ago by
- 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 8 years ago by
- Status changed from needs_work to needs_review
Ah, yes. Hope another cumulative patch is okay.
comment:27 Changed 8 years ago by
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 8 years ago by
- Description modified (diff)
Thanks :)
Patchbot: apply combined.patch
Changed 8 years ago by
comment:29 Changed 8 years ago by
Patchbot apply combined.patch
comment:30 Changed 8 years ago by
Looks good, thanks! Waiting on doctests to finish..
comment:31 Changed 8 years ago by
- Status changed from needs_review to positive_review
All doctests pass.
comment:32 Changed 8 years ago by
- Work issues doctest, docstring deleted
comment:33 Changed 8 years ago by
- 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 8 years ago by
* ping *
comment:35 Changed 8 years ago by
I'll provide a reviewer patch for this.
comment:36 Changed 8 years ago by
- 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 8 years ago by
- Status changed from needs_review to positive_review
comment:38 Changed 8 years ago by
- Milestone changed from sage-5.6 to sage-5.7
comment:39 Changed 8 years ago by
- Description modified (diff)
comment:40 Changed 8 years ago by
- Merged in set to sage-5.7.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
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?