patchGNU Octave - Patches: patch #9897, Implement the missing ordqz...

 
 

patch #9897: Implement the missing ordqz function.

Submitter:  Martin K <grisu86>
Submitted:  Tue 25 Feb 2020 10:01:44 AM 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

Tue 01 Dec 2020 06:50:16 PM UTC, comment #19: 

Seems to be working.

Closing as done.

Markus Mützel <mmuetzel>
Group administrator
Fri 23 Oct 2020 02:14:47 PM UTC, comment #18: 

@Martin: I can only extend on Philip's assessment. It was quite easy to review because the quality was very good from the start (style, documentation, tests, ...).

There are probably a few other gems hidden deep inside the bug and patch trackers. It's only a question of finding them. Thanks go to Philip for undiging this one.

@Philip: You'll probably see a few conflicts when updating. That's life for an early adopter I guess. ;-)
I often `hg strip --keep rev` in cases like these and try to resolve manually. But everyone found there way of dealing with conflicting changes I guess...

Markus Mützel <mmuetzel>
Group administrator
Fri 23 Oct 2020 01:41:20 PM UTC, comment #17: 

@Martin:
Very good to replace the test! thanks.
I found the patch /cset a very good piece of work, very complete, including tests and (except or a few instance) adhering to Octave coding style. Nice!

@Markus:
I'm curious what will happen with my local build tree when I do
"hg -v pull && hg -v merge"
Hopefully not too many merge conflicts. I'll see ... :-)

Philip Nienhuis <philipnienhuis>
Group Member
Fri 23 Oct 2020 01:17:22 PM UTC, comment #16: 

I pushed your change here:
https://hg.savannah.gnu.org/hgweb/octave/rev/69ec8d9e769b

Marking as ready for test.

Markus Mützel <mmuetzel>
Group administrator
Fri 23 Oct 2020 12:53:00 PM UTC, comment #15: 

@Markus
Good that the test now works.

Yes the name is correct. Being mentioned there is a nice to have in my academic CV ;-)

Martin K <grisu86>
Fri 23 Oct 2020 12:49:38 PM UTC, comment #14: 

@grisu86: Thanks for the updated test and for your contribution of this new function.
The new test passes for me. I'm going to replace the existing last test with this one.

Would you like to be added to the list of contributors of Octave that is shown at the beginning of the manual? Is "Martin Köhler" the correct writing of your name?

Markus Mützel <mmuetzel>
Group administrator
Fri 23 Oct 2020 12:40:45 PM UTC, comment #13: 

@philipnienhuis

I only include the test from the matlab homepage since this one was claimed in the early developments. I created an alternative

A = toeplitz([1,2,3,4]);
[B, A] = qr(A); B = B';
[AA,BB,Q,Z] = qz(A,B);
[AAS,BBS,QS,ZS] = ordqz(AA,BB,Q,Z,'lhp');
E2 = ordeig(AAS,BBS);
ECOMP = [ -3.414213562373092e+00 -1.099019513592784e+00     -5.857864376269046e-01 9.099019513592784e+00];
assert(norm(ECOMP - E2, 'Inf') < 1e-8);

It should check the same path in the code.


Martin K <grisu86>
Fri 23 Oct 2020 11:47:48 AM UTC, comment #12: 

@Markus:
You're right, other than stated in comment the patch probably didn't apply cleanly last time I applied it.
Looking back I wasn't aware of grisu86's final fix, somehow stumbled on it (maybe while searching because I needed ordqz) and then applied it maually.

The log of my (quite old, started on June, 14) local-mods-build tree, shows I have applied 3 csets in the following order:

  1. patch_9897_ordqz_function_v3.cset (AFAICS based on original patch, comitted after fixing a few failed hunks)
  2. 28478.patch (add missing file, N.B. ordqz.cc itself :-) )
  3. 28484.patch (fixed the actual bug in original patch + an extra test, see below).

All attached here for reference.
Together they I think should be equivalent to the first patch + changes in 2nd patch, rather than the second patch itself.

Now, as to that last test you give in comment #11:

(1) That very test IS largely the example on the matlab ordqz page so it should be dropped or replaced by another one.
(@grisu86: we can't use copyrighted material in Octave, but we can compare Octave with publicly published Matlab results.)

(2) When run manually it gives (on Windows 10):

>> assert (norm (ECOMP - E2, "Inf"), 0, 1e-8);
error: ASSERT errors for:  assert (norm (ECOMP - E2, "Inf"),0,1e-8)

  Location  |  Observed  |  Expected  |  Reason


To your relief I think the FAIL is probably either a tolerances issue or a faulty test; I manually compared the output on that Matlab web page with what ordqz() in Octave madkes from it. Re-running it again today gives identical results as Matlab but -as stated before- with sign differences, the latter already in the output of Octave's qz() function so probably not due to ordqz.

I'd happily try your patch (patch9897_ordqz_v2.patch) (could do somewhere in between the scenes, or later tonight), but do you think it's still needed with the above info?


(file #50066, file #50067, file #50068)

Philip Nienhuis <philipnienhuis>
Group Member
Fri 23 Oct 2020 09:12:09 AM UTC, comment #11: 

@Philip: Are you sure you used the latest patch (file #48923)? That one had a few missing semicolons in the last test and you should see that in the output (unless you added those semicolons manually).
Also there should be a total of 28 tests in that file.

Maybe even better would be to test the cleaned up patch I uploaded yesterday.

What do you see if you execute that test directly on Octave?

A = magic (5);
B = hilb (5);
[AA, BB, Q, Z] = qz (A, B);
[AAS, BBS, QS, ZS] = ordqz (AA, BB, Q, Z, "rhp");
E2 = ordeig (AAS, BBS);
ECOMP = [2.887137073068260e+06; 4.873038494509828e+02; 4.363814079693997e+01; -2.573723338161374e+04; -8.557816814087249e+02];
assert (norm (ECOMP - E2, "Inf"), 0, 1e-8);


Markus Mützel <mmuetzel>
Group administrator
Fri 23 Oct 2020 06:19:25 AM UTC, comment #10: 

... and just to be complete & sure, this morning on Mageia 7:

[philip@deskprn oct700+]$ make -j4 && make check && make dist
:
  libinterp/corefcn/oct-map.cc-tst ............................... pass   10/10
  libinterp/corefcn/ordqz.cc-tst ................................. pass   27/27
  libinterp/corefcn/ordschur.cc-tst .............................. pass    4/4
  libinterp/corefcn/pinv.cc-tst .................................. pass   17/17
:


Philip Nienhuis <philipnienhuis>
Group Member
Thu 22 Oct 2020 08:53:21 PM UTC, comment #9: 

FWIW, with __run-test_suite__ on my win10 box with a dev Octave crossbuild from just 15 minutes go I see this:


:
  libinterp\corefcn\oct-map.cc-tst ............................... pass   10/10
  libinterp\corefcn\ordqz.cc-tst ................................. pass   27/27
  libinterp\corefcn\ordschur.cc-tst .............................. pass    4/4
:


I usually do "make -j4 && make check && make dist" for the Linux builds before using the dist archive for crossbuilds, I can't remember having seen an ordqz FAIL there.
Just the (for me) usual 4 graphics FAILs because I have the datacursor patches in.

What OS & release do you run Markus?

Philip Nienhuis <philipnienhuis>
Group Member
Thu 22 Oct 2020 06:53:47 PM UTC, comment #8: 

Thank you for your contribution.
I slightly adapted the coding style (mostly white spaces and double quotes instead of single quotes) and added a commit message. Please, see the attached patch.

The last test is failing for me:

>> A = magic (5);
B = hilb (5);
[AA, BB, Q, Z] = qz (A, B);
[AAS, BBS, QS, ZS] = ordqz (AA, BB, Q, Z, "rhp");
E2 = ordeig (AAS, BBS);
ECOMP = [2.887137073068260e+06; 4.873038494509828e+02; 4.363814079693997e+01; -2.573723338161374e+04; -8.557816814087249e+02];
assert (norm (ECOMP - E2, "Inf"), 0, 1e-8);

error: ASSERT errors for:  assert (norm (ECOMP - E2, "Inf"),0,1e-8)

  Location  |  Observed  |  Expected  |  Reason
     ()       5.7407e-06       0         Abs err 5.7407e-06 exceeds tol 1e-08 by 6e-06


Is this just an accuracy issue and the tolerance should be increased? Or is there something more to it?

When this is fixed, it like to push this patch. Would you like to be added to the list of contributors?

(file #50054)

Markus Mützel <mmuetzel>
Group administrator
Tue 20 Oct 2020 12:01:31 PM UTC, comment #7: 

Forgot to set status, apologies.

I have tried it a few times for my own purposes (er simple ones) and see no issues with it.
The example on the Matlab help page gives identical results, except for some signs but AFAICS those sign differences stem from Octave' own magic, hilb or qz functions (these differences were there before invoking ordqz).

I'm unsure if it still applies cleanly but last time I started a new mxe-octave build tree with patched local dev Octave (~end of August) it did apply anyway (no bad hunks).

S,o as far as I am concerned this patch can be accepted.

Philip Nienhuis <philipnienhuis>
Group Member
Sun 14 Jun 2020 11:00:58 AM UTC, comment #6: 

Status to "ready for test".

Philip Nienhuis <philipnienhuis>
Group Member
Sun 14 Jun 2020 10:57:57 AM UTC, comment #5: 

@Martin:
Sorry I missed your update, I wasn't in the cc list. AFAIK that used to automatically add commenter's emails.
Sorry for that :-)

I'm just starting a new Octave 7.0.0 "local" build ("local" in the sense that I include several local mods and path trials) so I'll try your patch as well. After the Linux build I'll make an mxe-octave crossbuild to further try on Windows (where I use Octave the most).

Philip Nienhuis <philipnienhuis>
Group Member
Fri 24 Apr 2020 10:42:30 AM UTC, comment #4: 

I found the bug and added a new test to cover this as well.

The reason was around line 440:

 if ( k < nn-1 && aa(k+1,k) == 0.0 )

where for k == n-1 it was automatically assumed that the corresponding eigenvalue is complex, which is not true in general. I changed it to

 if ( ( k < nn-1 && aa(k+1,k) == 0.0 ) ) || k == nn-1 )


Then everything works and with enabled sanitizer no problems occur.

The fixed patch is attached.

(file #48923)

Martin K <grisu86>
Thu 23 Apr 2020 05:17:22 PM UTC, comment #3: 

Same on Linux, hard crash.

Status -> bug

Philip Nienhuis <philipnienhuis>
Group Member
Thu 23 Apr 2020 05:12:05 PM UTC, comment #2: 

On Windows, reference BLAS or OpenBLAS makes no difference.

I suppose this patch will make it in Octave-7.0.0 at the earliest so it should run fine in dev Octave.

Philip Nienhuis <philipnienhuis>
Group Member
Thu 23 Apr 2020 04:34:20 PM UTC, comment #1: 

Thanks for the patch.
I've included in my mxe-octave builds for a while but only now got round to testing it.

I tried the example here:
https://nl.mathworks.com/help/matlab/ref/ordqz.html

All goes well until the actual call to ordqz, and then Octave-7.0.0 crashes and vanishes w/o a trace. It must be quite a serious one so that even Windows can't catch it with its "program has crashed" dialog.
So no joy:-(

Late tonight I'll try Linux as well.

Philip Nienhuis <philipnienhuis>
Group Member
Tue 25 Feb 2020 10:01:44 AM UTC, original submission:  

I implemented the ordqz function which is still missing in Octave. Until now, Octave says that it is not implemented yet. The function follows the calling sequence of its MATLAB counterpart but also allows the keywords used by the reordering functionallity of Octave's qz function. The patch includes documentation and a set of software tests. The reordering works for real and complex data using the {D,Z}TGSEN function of LAPACK.


Martin K <grisu86>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #50066:  patch_9897_ordqz_function_v3.cset added by philipnienhuis (4KiB - application/octet-stream)
file #50067:  28478.patch added by philipnienhuis (21KiB - application/octet-stream)
file #50068:  28484.patch added by philipnienhuis (664B - application/octet-stream)
file #50054:  patch9897_ordqz_v2.patch added by mmuetzel (26KiB - application/octet-stream)
file #48923:  octave-ordqz-fixed.diff added by grisu86 (27KiB - text/x-patch)
file #48496:  octave-ordqz.patch added by grisu86 (25KiB - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by mmuetzel (Updated the item)
  • -email is unavailable- added by philipnienhuis
  • -email is unavailable- added by grisu86 (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 16 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2020-12-01 mmuetzel StatusReady For Test Done
        Open/ClosedOpen Closed
    2020-10-23 mmuetzel StatusIn Progress Ready For Test
    2020-10-23 mmuetzel StatusNeed Info In Progress
    2020-10-23 philipnienhuis Attached File- Added patch_9897_ordqz_function_v3.cset, #50066
        Attached File- Added 28478.patch, #50067
        Attached File- Added 28484.patch, #50068
    2020-10-22 mmuetzel Attached File- Added patch9897_ordqz_v2.patch, #50054
        StatusReady For Test Need Info
    2020-10-20 philipnienhuis StatusNone Ready For Test
    2020-07-11 mtmiller StatusReady For Test None
    2020-06-14 philipnienhuis StatusBug Ready For Test
    2020-06-14 philipnienhuis Carbon-Copy- Added philipnienhuis
    2020-04-24 grisu86 Attached File- Added octave-ordqz-fixed.diff, #48923
    2020-04-23 philipnienhuis StatusNone Bug
    2020-02-25 grisu86 Attached File- Added octave-ordqz.patch, #48496

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code