bugGNU Octave - Bugs: bug #57968, condest produces incorrect result...

 
 

bug #57968: condest produces incorrect result for any matrix that is not symmetric/Hermitian

Submitter:  Brian Sutton <briansutton>
Submitted:  Sat 07 Mar 2020 11:26:23 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * 6.0.90 Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Fri 13 Mar 2020 05:51:11 PM UTC, comment #4: 

As an addendum, I overhauled the condest.m function on the development branch that will become Octave 7.1.  See changeset https://hg.savannah.gnu.org/hgweb/octave/rev/687d452070c9.

In particular, I cache the result of certain long matrix operations such as


Ainvt = P' * (L' \ (U' \ Q'));


so they are calculated just once per estimate.  Previously, this same calculation would be repeated up to 5 times per estimate.

Rik <rik5>
Group administrator
Wed 11 Mar 2020 10:49:08 PM UTC, comment #3: 

Thank you!

Brian Sutton <briansutton>
Wed 11 Mar 2020 08:14:03 PM UTC, comment #2: 

Verified that the problem was with condest.m as you outlined.  I checked in a fix here https://hg.savannah.gnu.org/hgweb/octave/rev/4609d001daee.  This is on the stable branch which will become the next 6.1 release soon.  I also added BIST tests for sparse and full inputs so this behavior isn't re-introduced in the future.

Thanks for identifying this and reporting it.  Marking as fixed and closing report.

Rik <rik5>
Group administrator
Wed 11 Mar 2020 04:24:52 PM UTC, comment #1: 

Confirmed. 

I think there needs to be a little bit more digging to figure out whether it is condest.m which is incorrectly setting up the solver function, or whether it is the algorithm in normest1 which is calling the solver incorrectly (with "notransp" or "transp" set to the opposite value).

Rik <rik5>
Group administrator
Sat 07 Mar 2020 11:26:23 PM UTC, original submission:  

In the condest function, the input matrix and its transpose are swapped at one point, leading to incorrect results.

Demonstration:


octave:1> A = reshape(sqrt(0:15),4,4);
octave:2> % Desired result:
octave:3> norm(A,1)*norm(inv(A),1)
ans =  49422.61476
octave:4> % Output of condest:
octave:5> condest(A)
ans =  52089.95402
octave:6> % What condest is actually computing:
octave:7> norm(A,1)*norm(inv(A'),1)
ans =  52089.95402


Note that in line 3, it's inv(A), but in line 7, it's inv(A').

Fix:

1. In scripts/linear-algebra/condest.m function solve_sparse, swap line 242
    case "notransp"
and line 244
    case "transp"
2. In scripts/linear-algebra/condest.m function solve_not_sparse, swap line 255
    case "notransp"
and line 257
    case "transp"


Brian Sutton <briansutton>

 

(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

Digest:
   bug dependencies.

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by briansutton (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 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2020-05-09 mtmiller Dependencies- bugs #58339 is dependent
    2020-03-11 rik5 StatusConfirmed Fixed
        Open/ClosedOpen Closed
    2020-03-11 rik5 StatusNone Confirmed
        Release5.2.0 6.0.90

    Back to the top

    Powered by Savane 3.13-758e.
    Corresponding source code