bugGNU Octave - Bugs: bug #66057, ordqz sometimes fails to produce...

 
 

bug #66057: ordqz sometimes fails to produce correct result if called repeatedly

Submitter:  Anders Helmersson <ahelmersson>
Submitted:  Fri 02 Aug 2024 12:27:01 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Confirmed Assigned to:  None
Originator Name:  Anders Helmersson Open/Closed:  * Open
Release:  * 7.3.0 Operating System:  * GNU/Linux
Fixed Release:  None Planned Release:  9.3.0 (current stable)
* Mandatory Fields

Add a New Comment Rich Markup
   

Fri 09 Aug 2024 06:49:44 AM UTC, comment #5: 

DHGEQZ is used to find the complex eigenvalues of the 2x2 blocks on the diagonal in real A and B so that qzord can select the appropriate blocks to reorder, for instance those in the right half plane.

The local copies of A and B in the call to DHGEQZ need to be two 2x2 matrices only and the same local variables can be used in the loop (allocated before the loop).

Instead of calling DHGEQZ, it is possible to compute the complex eigenvalues using an algorithm similar to the one defined in ordeig.m.

Anders Helmersson <ahelmersson>
Thu 08 Aug 2024 05:53:43 PM UTC, comment #4: 

Confirmed.  I checked the LAPACK routine for DHGEQZ and the Fortran routine requires that aa, bb inputs are in/out.  The documentation definitely refers to returning some results in these bidirectional function parameters.

One solution would be to use a local variable for aa and bb.  However, I note that the call to DHGEQZ is within a loop


while (k < nn)


which runs from 0 to the number of rows in the matrix in steps of 2.  Currently, the local version of 'aa' is initialized just once.  But if we change to initializing the local version every time there will be nr/2 iterations and nr^2 elements to copy per initialization.  This doesn't seem ideal.

Is Octave using the right algorithm?

I notice that for complex aa,bb the code simply calls ZTSGEN.  But for real cases, the code runs this loop which repeatedly calls DHGEQZ and then after all that work is done it calls DTSGEN.  Is there a way to just call DTSGEN once and skip the rest?

Rik <rik5>
Group administrator
Sat 03 Aug 2024 05:03:06 AM UTC, comment #3: 

The problem remains in octave 9.2.

It is necessary to modify the first qz call in my example by adding the 'real' option, in order to produce 2x2 blocks in aa and bb

tol = 1e-13;
[aa, bb, q, z] = qz (a, b,'real');
[aaa, bbb, qq, zz] = ordqz (aa, bb, q, z, [0 0 1 1]);
[aaaa, bbbb, qqq, zzz] = ordqz (aaa, bbb, qq, zz, [0 0 1 1]);
assert (norm (aaaa - qqq a zzz) < tol);

Anders Helmersson <ahelmersson>
Fri 02 Aug 2024 06:28:42 PM UTC, comment #2: 


there was some changes for octave 9


warning: qz: returns the complex QZ by default on real matrices since version 9
warning: called from
    test33371 at line 26 column 16

ans =

   0.0000 - 2.9278i
  -0.0000 + 2.9278i
   0.5916 - 0.0000i
  -0.5916 +      0i

>> ver

----------------------------------------------------------------------
GNU Octave Version: 9.1.1 (hg id: c59ff2782e04)
GNU Octave License: GNU General Public License
Operating System: Linux 6.8.0-39-generic #39-Ubuntu SMP PREEMPT_DYNAMIC Fri Jul  521:49:14 UTC 2024 x86_64

Doug Stewart <dastew>
Fri 02 Aug 2024 05:41:56 PM UTC, comment #1: 

I can reproduce with 8.4.0 but not with 9.2.1

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Fri 02 Aug 2024 12:27:01 PM UTC, original submission:  

The function ordqz is used to move eigenvalue blocks in the triangular A and B matrices obtained from qz.

If called repeatedly using the select vector, which is sometimes needed, the result may become unreliable. The code snippet below fails.


tol = 1e-13;

a = [ 0   0   1  -2
      0  -2   0  -1
      1   0  -4   1
     -2  -1   1  -2];

b = [ 0  -1   2   2
      1   0   0  -1
     -2   0   0  -1
     -2   1   1   0];

[aa, bb, q, z] = qz (a, b);
ordeig (aa, bb)

[aa, bb, q, z] = ordqz (aa, bb, q, z, [0 0 1 1]);
assert (norm (aa - q * a * z) < tol);  % succeeds

[aa, bb, q, z] = ordqz (aa, bb, q, z, [0 0 1 1]);
assert (norm (aa - q * a * z) < tol);  % fails


During the check and extraction of eigenvalues in ordqz.cc, 2x2 blocks are passed as arguments to DHGEQZ. This might modify the corresponding 2x2 blocks in aa and bb, but the remaing rows and columns are not affected, neither qq nor zz. This seems to cause the problem.                                           
                                                                               
FIX: copy the 2x2 blocks in aa and bb to local 2x2 matrices before           
calling DHGEQZ, instead of operating on aa and bb directly.

I am using version 7.3.0 but the problem seems to remain in later versions as well.                   

Anders Helmersson <ahelmersson>

 

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

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by dastew (Posted a comment)
  • -email is unavailable- added by dasergatskov (Posted a comment)
  • -email is unavailable- added by ahelmersson (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 group members can vote.

     

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2024-08-08 rik5 StatusNone Confirmed
        Planned ReleaseNone 9.3.0 (current stable)

    Back to the top

    Powered by Savane 3.14-3b9d.
    Corresponding source code