patchGNU Octave - Patches: patch #8837, normest1

 
 

patch #8837: normest1

Submitter:  Marco Caliari <caliari>
Submitted:  Mon 21 Dec 2015 03:15:13 PM UTC
   
 
Category:  Core : new function Priority:  5 - Normal
Status:  Done Privacy:  Public
Assigned to:  None Open/Closed:  Closed
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Sat 30 Jul 2016 01:32:51 PM UTC, comment #21: 

Fixed the last issue with this change http://hg.savannah.gnu.org/hgweb/octave/rev/e35866e6a2e0

I don't think this is very important, this variable probably won't be used anywhere where it's shape matters. But it's good to be consistent.

Note that this is Matlab incompatible by design.

Carnë Draug <carandraug>
Group Member
Tue 26 Jul 2016 11:41:24 AM UTC, comment #20: 

Because the main code path returns k as a column vector (it's only the optional optimization for n < 4 that returns a row vector), then that's probably the most expected so I'd say to change it to always be a column vector.  If I was at Mathworks and had to change this, I'd go with that too as the one that would be most backwards compatible.

Carnë Draug <carandraug>
Group Member
Tue 26 Jul 2016 11:33:00 AM UTC, comment #19: 

I have pushed http://hg.savannah.gnu.org/hgweb/octave/rev/bfb1b089c230 as discussed on IRC.

I noticed that none of the tests in normest1 check the value of k. Could you add tests for that?

One other thing is that k is a row or column vector depending on the code path took (it's a row vector if ((n <= 4) || (t == n))).  I understand that this is Matlab compatible but is also obviously a Matlab bug.

Does anyone has an opinion about making it always one or the other? And if so, which? A row or a column vector?

Carnë Draug <carandraug>
Group Member
Mon 25 Jul 2016 09:46:48 AM UTC, comment #18: 

Looks good to me.  Will you prepare a cset that adds the file to the build, remove the deprecated functions from the manual, move them to the deprecated directory and make them throw deprecated warnings?

Carnë Draug <carandraug>
Group Member
Mon 25 Jul 2016 09:06:17 AM UTC, comment #17: 

From IRC, we (Carnë and I) agreed on the following:

1) onenormest deprectaed
2) normest1 Matlab compatible and supporting the syntax (although deprecated) of onenormest
3) condest supporting the new syntax of normest1 and the old syntanx (although deprecated) of onenormest

I did the following:

2) normest1 detects the syntax and if it is onenormest syntax, it issues a warning and call its subfunction onenormest

3) condest detects the syntax and if it is onenomrmest syntax, it issues a warning and call its subfunction condest_legacy (which is 4.0.x condest). onenormest is a subfunction as well.

(file #38018, file #38019)

Marco Caliari <caliari>
Group Member
Fri 15 Jul 2016 12:15:07 PM UTC, comment #16: 

condest could be modified in order to use normest1. The syntax should be changed, using AFUN like in normest1 instead of APPLY and APPLY_T. This does not break the compatibility with Matlab (whose condest cannot be applied to functions), but with the previous versions of Octave. In order to summirize, we currently have:

1) onenormest, normest1 working both with matrices (same syntax) and with functions (different syntax), normest1 compatible with Matlab

2) condest (estimates the condition number in norm 1) working both with matrices (compatible with Matlab) and with functions (not supported in Matlab), with syntax compatible with onenormest.

3) normest (estimates the norm 2) working with matrices (compatible with Matlab), easy to extend to functions (not supported in Matlab) with the same syntax of normest1.

A final situation (for me) could be:

1) condest1=condest, for matrices and functions, using normest1.
2) normest2=normest, for matrices and functions

The first step should be making deprecated onenormest and the current syntax of condest. Sounds reasonable?

Marco Caliari <caliari>
Group Member
Fri 15 Jul 2016 10:53:30 AM UTC, comment #15: 


> Should be onenormest become deprecated? It is not in Matlab and doing essentially the same as normest1, with a different syntax.


Yes probably. Maybe moved to the linear-algebra package would be better but onenormest is used in condest. Yes definitely if we add normest1.

If the two functions do the same thing, and if we need one of them because of condest, and if normest1 is in Matlab (even if undocumented) but onenormest is not, then I'm ok with having normest1 instead.

Carnë Draug <carandraug>
Group Member
Fri 15 Jul 2016 09:22:11 AM UTC, comment #14: 

Should be onenormest become deprecated? It is not in Matlab and doing essentially the same as normest1, with a different syntax.

Marco Caliari <caliari>
Group Member
Thu 14 Jul 2016 05:47:02 AM UTC, comment #13: 

Carnë, As Marco said, the "est" value is the first return value of normest1:


function [est, v, w, k] = normest1(A, t = 2, X, varargin)


Lachlan Andrew <lachlan>
Thu 14 Jul 2016 05:32:00 AM UTC, comment #12: 

Albeit undocumented, current Matlab must still have normest1, since Higham says that it is called by sqrtm: https://nickhigham.wordpress.com/2016/04/05/improved-matlab-function-sqrtm/

Nir Krakauer <nir_krakauer>
Wed 13 Jul 2016 05:22:55 PM UTC, comment #11: 

Why not the second point? On line 96 you have


      [est, idx] = max (sum (abs (A)));


but that "est" value is never used. So why not [~, idx] = max (sum (abs (A))) ?


There's a few other style changes but I can make them myself after you push (but can you unindent the "endfunction"?)

Also, I just found that while this function seems to be on Matlab R2010b, I's no longer on their online documentation. I don't see mention on the release notes about its removal. Is this an undocumented function or have they replaced with something else?

Carnë Draug <carandraug>
Group Member
Tue 12 Jul 2016 07:15:29 AM UTC, comment #10: 

I applied all the changes, execpt the first two. For compatibility, normest1(A,[],X) should use t=2. Then, est in [est,idx] = ... is the first output argument.

(file #37821)

Marco Caliari <caliari>
Group Member
Fri 08 Jul 2016 12:25:17 PM UTC, comment #9: 

Copied from IRC:

  • instead of "if ((nargin <= 1) || isempty (t)), t = 2" you can just do "function [est, v, w, k] = normest1(A, t = 2, X, varargin)"
  • when you do "[est, idx] = max (sum (abs (A)))" but then don't use est, use '[~, idx] = ...'. Also, it's a good idea to specify the dimension on sum() and max()
  • instead of 'X = X / n', use 'X /= n' which is reduces memory usage
  • use ! instead of ~
  • estold should probably be est_old since that's two words, same with possiblebreak
  • do not use hard tabs. Use spaces only. The code looks wrong on my system because hard tabs are 2 spaces and other people will also have different setup than yours
  • what's the purpose of this code? It does nothing https://bpaste.net/show/d6fb97659aa5
  • this loop could be easily vectorized https://bpaste.net/show/5475ca4e2c04
  • you should remove trailing whitespace. There's a lot of it
  • when it comes to texinfo, you should use @dots instead ...
  • also, don't use empty lines yourself, you can write lists on texinfo too
  • instead of making the uppercase yourself on '@code{AFUN (FLAG, X)}', use @var. Note that the purpose of @var is not to uppercase text. That effect is only for terminal output.
Carnë Draug <carandraug>
Group Member
Thu 07 Jul 2016 01:25:03 AM UTC, comment #8: 

You say "please", but I don't have permission to push.  I assumed that you did, since Rik said you're the dev most interested in linear algebra.

Is there anything I can help with?

Lachlan Andrew <lachlan>
Wed 06 Jul 2016 02:26:27 PM UTC, comment #7: 

Yes, please.

Marco Caliari <caliari>
Group Member
Wed 06 Jul 2016 01:50:16 PM UTC, comment #6: 

Marco, do you want to apply this before the 4.2.0 feature freeze?

Lachlan Andrew <lachlan>
Tue 19 Apr 2016 08:42:55 PM UTC, comment #5: 

Dear Marco,

I added your file normest1.m in Octave and I made a Mercurial changeset, I attach the file added-normest1.diff.

Chiara

(file #36964)

Chiara Segala <chiarasegala>
Thu 11 Feb 2016 03:20:41 PM UTC, comment #4: 

Updated version (copyright 2016).

(file #36317)

Marco Caliari <caliari>
Group Member
Wed 10 Feb 2016 12:07:59 PM UTC, comment #3: 

Hi Mike,

onenormest is not compatible with matlab (not only in the name), so my file is still relevant. However, I discovered later that there is still something to change, and I will do it in the next days. Thanks.

Marco Caliari <caliari>
Group Member
Tue 09 Feb 2016 11:32:05 PM UTC, comment #2: 

Marco, have you gotten what you needed from the onenormest function or is your patch still relevant?

Mike Miller <mtmiller>
Group Member
Mon 21 Dec 2015 03:35:54 PM UTC, comment #1: 

I realize NOW that there is already onenormest in Octave, never heard of it before! I will give a look.

Marco

Marco Caliari <caliari>
Group Member
Mon 21 Dec 2015 03:15:13 PM UTC, original submission:  

I wrote the function normest1, which estimates the 1-norm of a matrix. It is based on Algorithm 2.4 of "A block algorithm for matrix 1-norm estimation, with an application to 1-norm pseudospectra", by N. J. Higham and F. Tisseur. The function call is the same as Matlab's normest1. I checked the implementation by trying to reproduce the tables included in the paper (see my testnormest1.m). The results are quite satisfactory. Matlab's normest1 is usually faster (in term of iterations), but produces much less exact results. It seems to me that the exit criteria were relaxed in favor of speed of "convergence".

Marco Caliari <caliari>
Group Member

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #38018:  normest1.m added by caliari (15KiB - text/x-objcsrc)
file #38019:  condest.m added by caliari (16KiB - text/x-objcsrc)
file #37821:  normest1.m added by caliari (9KiB - application/binary)
file #36964:  added-normest1.diff added by chiarasegala (10KiB - text/x-patch)
file #36317:  normest1.m added by caliari (9KiB - application/binary)
file #35825:  normest1.m added by caliari (9KiB - application/vnd.wolfram.mathematica.package)
file #35826:  testnormest1.m added by caliari (1KiB - application/vnd.wolfram.mathematica.package)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by nir_krakauer (Posted a comment)
  • -email is unavailable- added by lachlan (Posted a comment)
  • -email is unavailable- added by chiarasegala (Updated the item)
  • -email is unavailable- added by mtmiller (Posted a comment)
  • -email is unavailable- added by caliari (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 11 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-07-30 carandraug StatusNeed Info Done
        Open/ClosedOpen Closed
    2016-07-25 caliari Attached File- Added normest1.m, #38018
        Attached File- Added condest.m, #38019
    2016-07-12 caliari Attached File- Added normest1.m, #37821
    2016-07-07 lachlan CategoryNone Core : new function
    2016-04-19 chiarasegala Attached File- Added added-normest1.diff, #36964
    2016-02-11 caliari Attached File- Added normest1.m, #36317
    2016-02-09 mtmiller StatusNone Need Info
    2015-12-21 caliari Attached File- Added normest1.m, #35825
        Attached File- Added testnormest1.m, #35826

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code