bugGNU Octave - Bugs: bug #34173, Unary negative casts permutation...

 
 

bug #34173: Unary negative casts permutation matrices into full matrices

Submitter:  Mikael <mandolin>
Submitted:  Tue 30 Aug 2011 11:03:40 AM UTC
 
Category:  Libraries Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Confirmed Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * dev Operating System:  * GNU/Linux
* Mandatory Fields

Add a New Comment (Rich Markup)
   

Comment Type & Canned Response:
       

 

( Jump to the original submission )

Sun 20 Dec 2020 01:21:58 PM UTC, comment #18: 

Yeah I didn't even know Octave used a sparse permutation type for memory efficiency.

I guess the whole bug thread suggests three options if this bug were to be "fixed"

1 preserve the perm. matrix and see if the reported bug can be fixed, where unary neg turns a perm into a full matrix.  it does seem odd for that seemingly simple operation to trigger expansion. This was attempted in comment #10 but reverted by Rik in comment #12 because bug #44316 found it was causing incorrect  comparison results, which obviously takes precedence over efficiency. Seems this fix would really require revisiting that bug solution.

2 comment #13 suggested leaving it alone, documenting somewhere not to rely on the memory efficiency of the permutation type and/or list the arithmetic and comparison ops that convert back to using the full memory requirement.

3 comment #16 hinted at doing away with permutation (and maybe othrr") memory saving data types to simplify the codebase and avoid problems like this report. I believe this was separately discussed for ranges not too long ago.

4 (implied) leave it as a won't fix. It's a 9 year old bug that isn't exactly reporting something broken, just unexpectedly imposing the "normal" memory requirement.

Nicholas Jankowski <nrjank>
Project Member
Sun 20 Dec 2020 03:47:31 AM UTC, comment #17: 

I like that Octave has additional features beyond Matlab.  And because this is already coded, I wouldn't discard it.  In this case, we are no worse than Matlab.  Matlab always uses full matrices for permutation matrices while Octave occasionally uses full matrices (for example when unary minus operator is applied), but lots of times can use the reduced memory implementation. 

Rik <rik5>
Project Administrator
Sat 19 Dec 2020 07:24:30 PM UTC, comment #16: 

AFAIK, Matlab doesn't have a special type for permutation matrices.  They are always full.  You can disable Octave's special data type for them by using

disable_permuation_matrix (true);

This setting is enabled by default if you start Octave with the --traditional option.

It would make Octave internals simpler if we just did this by default and eliminated the special type.  Likewise for diagonal matrices and ranges (the special data types for those may also be disabled).

John W. Eaton <jwe>
Project Administrator
Fri 18 Dec 2020 09:12:11 PM UTC, comment #15: 

behavior still present in Octaev 6.1.0.  other details same as comment #14

Nicholas Jankowski <nrjank>
Project Member
Thu 08 Dec 2016 04:23:01 AM UTC, comment #14: 

this behavior still exists in 4.2.0

the comment #12 commands just seem to produce full matrices in Matlab 2016b.  I'm unaware if matlab stores 'permutation matrices' through any other method or not to address Lachlan's question.

Nicholas Jankowski <nrjank>
Project Member
Wed 15 Jun 2016 08:31:19 AM UTC, comment #13: 

Is this really a bug?

In terms of Matlab compatibility, is there any sequence of instruction that produces a permutation matrix where Matlab doesn't produce a full matrix?  If not, then the behaviour is entirely up to us.

If the programmer wants a sparse matrix, it is easy to convert to sparse before negating.  They can't want a permutation matrix if it is negative.

Unless there is a Matlab compatibility issue, I would vote for documenting this behaviour and leaving it as-is.

Lachlan Andrew <lachlan>
Tue 24 Nov 2015 12:50:18 AM UTC, comment #12: 

The behavior of unary minus converting a Permutation Matrix to a Full Matrix has been re-introduced to solve bug #44316.  I am re-opening this bug report as it is now present on the development branch.  Test code

x = eye(3)(:,[1 3 2])
x =

Permutation Matrix

   1   0   0
   0   0   1
   0   1   0

octave:9> -x
ans =

  -1  -0  -0
  -0  -0  -1
  -0  -1  -0

Rik <rik5>
Project Administrator
Wed 31 Aug 2011 06:33:17 AM UTC, comment #11: 

Thank you.

I'll be waiting for the next release, since I'll be waiting for other updates as well (which I have read about).

I thought I report a bug when I found one.

Mikael <mandolin>
Tue 30 Aug 2011 11:46:09 PM UTC, comment #10: 

This changeset fixes the problem for me:

http://hg.savannah.gnu.org/hgweb/octave/rev/b646413c3d0e

It's a fairly large change I'm not 100% sure about and it's fixing a relatively minor and workaroundable bug, so I pushed it on the default branch.

To see this change, you will need to build from the development sources or wait for our next major stable release.

Jordi Gutiérrez Hermoso <jordigh>
Project Administrator
Tue 30 Aug 2011 03:51:33 PM UTC, comment #9: 

Btw, this is enough to reproduce it:

-Qq

It appears that Qq is a permutation matrix, which is stored sparsely, and attempting to make it negative tries to cast it from a permutation matrix to a full matrix, which is why you run out of memory.

The fix seems to be to make permutation matrices (an internal Octave type) first attempt a cast into sparse matrices into full matrices. I'll look into making this fix.

Jordi Gutiérrez Hermoso <jordigh>
Project Administrator
Tue 30 Aug 2011 03:43:32 PM UTC, comment #8: 

Thank you. I can reproduce the problem now. I'll investigate and attempt a fix if someone else doesn't beat me to it.

Jordi Gutiérrez Hermoso <jordigh>
Project Administrator
Tue 30 Aug 2011 02:15:11 PM UTC, comment #7: 

and the file... ziped...

(file #23909)

Mikael <mandolin>
Tue 30 Aug 2011 02:13:48 PM UTC, comment #6: 

Ok, I'll try again :P

hopefully both are in this file..

Mikael <mandolin>
Tue 30 Aug 2011 02:05:38 PM UTC, comment #5: 

Sorry to be such a bother, but you seem to have only saved the Y vector...

The save command should be:

     save -binary filename Y J

and that should produce a rather large file. You should be able to compress it with gzip or similar (please, no rar).

Jordi Gutiérrez Hermoso <jordigh>
Project Administrator
Tue 30 Aug 2011 01:06:18 PM UTC, comment #4: 

Oh sorry about that...

I have saved the J and Y in attached files, saved them as -binary hope I did it right..

(file #23908)

Mikael <mandolin>
Tue 30 Aug 2011 12:35:55 PM UTC, comment #3: 

You don't mean "crash". A crash is when the operating system sends a signal to a program to termminate immediately, because, for example, the program requested to use memory that the operating system hadn't assigned to it yet. You simply mean "Octave reports an error" or something like that.

The information contained in Q is crucial, because I need to know how much memory it's using, and I also need to know how much memory is available in your system. Please attempt to reproduce this problem with data that you can show me.

Jordi Gutiérrez Hermoso <jordigh>
Project Administrator
Tue 30 Aug 2011 12:13:49 PM UTC, comment #2: 

I saw that I forgot the error message..
Can't post all the code and all data sorry, but this is the basics:

[L,U,Pp,Qq,Rr]=lu(J);

Y = ... (a vector)
z1 = Rr\Y;
z2 = L\(Pp*z1);
z3 = U\z2;
dY =-(Qq*z3); (this is the step where it crashes)

without ()
dY =-Qq*z3;
the following message is posted
error: memory exhausted or requested size too large for range of Octave's index type -- trying to return to prompt

I have a sparce matrix J (have a spy as attachment) tried to use just
[L,U]=lu(J);
Y = ...
dY=-U\(L\Y);

this does not work good since octave gives
warning: matrix singular to machine precision, rcond = 1
warning: attempting to find minimum norm solution


Mikael <mandolin>
Tue 30 Aug 2011 11:57:43 AM UTC, comment #1: 

I can't reproduce the problem.

Can you show the actual code that is producing this? What are Q and x?

Jordi Gutiérrez Hermoso <jordigh>
Project Administrator
Tue 30 Aug 2011 11:03:40 AM UTC, original submission:  

I have found a strange problem.

I have a big sparse matrix Q  (43750 43750) and a vector x

then
Y = -Q*x;

gives the error message:

but with
Y = -(Q*x);
or
Z = Q*x;
Y = -Z;

works fine.. should give same results.

Mandolin

Mikael <mandolin>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #23909:  parameters.zip added by mandolin (1MiB - application/x-zip-compressed)
file #23908:  vector added by mandolin (276KiB - application/octet-stream)
file #23907:  spy.jpg added by mandolin (15KiB - image/jpeg)

 

Depends on the following items: None found

Digest:
   bug dependencies.

 

Carbon-Copy List
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by lachlan (Posted a comment)
  • -email is unavailable- added by ttl (Updated the item)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by rik5
  • -email is unavailable- added by jordigh (Posted a comment)
  • -email is unavailable- added by mandolin (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 project members can vote.

     

     

     

     

    Follow 17 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2015-11-25 ttl CategoryGUI Libraries
    2015-11-24 rik5 StatusFixed Confirmed
        Open/ClosedClosed Open
        Release3.4.2 dev
        Carbon-Copy- Added jwe
    2015-04-06 rik5 Dependencies- bugs #44316 is dependent
    2011-08-31 jordigh SummaryPossible bug with multiplification with matrices and "-" sign Unary negative casts permutation matrices into full matrices
    2011-08-30 jordigh StatusConfirmed Fixed
        Open/ClosedOpen Closed
        SummaryUnary negative casts permutation matrices into full matrices Possible bug with multiplification with matrices and "-" sign
    2011-08-30 jordigh SummaryPossible bug with multiplification with matrices and "-" sign Unary negative casts permutation matrices into full matrices
    2011-08-30 jordigh StatusWorks For Me Confirmed
    2011-08-30 mandolin Attached File- Added parameters.zip, #23909
    2011-08-30 mandolin Attached File- Added vector, #23908
    2011-08-30 mandolin Attached File- Added spy.jpg, #23907
    2011-08-30 jordigh Item GroupSegfault, Bus Error, etc. Incorrect Result
        StatusNone Works For Me

    Back to the top


    Powered by Savane 3.9