Crash in cond on large sparse matrix

Discussion:

Søren Hauberg

2006-06-24 18:40:28 UTC

Hi,
In trying to compute the condition number of a 10000x10000 sparse
matrix, but octave 2.9.6 crashes. The code is as follows:

m = 100;
n = m;
mn = m*n;
A = spdiag(4*ones(1,mn))
- spdiag(ones(1,mn-1), 1)
- spdiag(ones(1,mn-1), -1)
- spdiag(ones(1,mn-m), m)
- spdiag(ones(1,mn-m), -m);
cond(A)

After a lot of computations (approx. 20 min. on a fairly new laptop) I
get the following error:

*** glibc detected *** double free or corruption (out): 0x09054be0 ***
panic: Aborted -- stopping myself...
attempting to save variables to `octave-core'...
save to `octave-core' complete
Afbrudt (SIGABRT)

Søren

John W. Eaton

2006-06-25 14:15:18 UTC

Permalink

Post by SÃ¸ren Hauberg
- spdiag(ones(1,mn-1), 1)
- spdiag(ones(1,mn-1), -1)
- spdiag(ones(1,mn-m), m)
- spdiag(ones(1,mn-m), -m));

octave:5> cond(A)
ans = 8261.8

I don't think there have been any changes to the sparse code since we
made the 2.9.6 snapshot so I think you need to provide more
information (always a good idea anyway). What BLAS/LAPACK are you
using? what kind of system do you have? How was Octave compiled? It
would be best to use the bug_report function as all that information
is included in the report.

jwe

Søren Hauberg

2006-06-25 14:45:01 UTC

Permalink

Post by SÃ¸ren Hauberg
- spdiag(ones(1,mn-1), 1)
- spdiag(ones(1,mn-1), -1)
- spdiag(ones(1,mn-m), m)
- spdiag(ones(1,mn-m), -m));

octave:5> cond(A)
ans = 8261.8
I don't think there have been any changes to the sparse code since we
made the 2.9.6 snapshot so I think you need to provide more
information (always a good idea anyway). What BLAS/LAPACK are you
using? what kind of system do you have? How was Octave compiled? It
would be best to use the bug_report function as all that information
is included in the report.

Okay, I'm sorry about the missing information. I'm attaching the
information from bug_report().

I looked at the code and cond() calls svd(). I don't see a sparse
implementation of svd() so I'm guessing it's not relevant that the
matrix is sparse. This problem is propably triggered by the machine
running out of memory (I only have 512MB). I'm guessing you'll trigger
the bug on your machine if you increase the m variable.

SÃžren

John W. Eaton

2006-06-25 15:14:59 UTC

Permalink

On 25-Jun-2006, Søren Hauberg wrote:

| Okay, I'm sorry about the missing information. I'm attaching the
| information from bug_report().
|
| I looked at the code and cond() calls svd(). I don't see a sparse
| implementation of svd() so I'm guessing it's not relevant that the
| matrix is sparse. This problem is propably triggered by the machine
| running out of memory (I only have 512MB). I'm guessing you'll trigger
| the bug on your machine if you increase the m variable.

What LAPACK and BLAS libraries are you using? ATLAS?

How much memory does your system have?

If I increase m to 200, I see the following crash:

octave:1> m = 200;
octave:2> n = m;
octave:3> mn = m*n;
octave:4> A = (spdiag(4*ones(1,mn))

Post by SÃ¸ren Hauberg
- spdiag(ones(1,mn-1), 1)
- spdiag(ones(1,mn-1), -1)
- spdiag(ones(1,mn-m), m)
- spdiag(ones(1,mn-m), -m));

octave:5> cond(A)

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 46912574002112 (LWP 26342)]
0x00002aaaaba57399 in SparseMatrix::matrix_value (this=<value optimized out>)
at /home/jwe/src/octave/liboctave/dSparse.cc:7789
7789 retval.elem (ridx(i), j) = data (i);
Current language: auto; currently c++
(gdb) p ridx
Cannot access memory at address 0x0
(gdb) p data
Cannot access memory at address 0x0
(gdb) p retval
$1 = (Matrix &) @0x7ffffff9d9a0: {
<MArray2<double>> = {
<Array2<double>> = {
<Array<double>> = {
_vptr.Array = 0x2aaaab5cd750,
rep = 0x181bd30,
dimensions = {
rep = 0x181b680
},
idx = 0x0,
idx_count = 0
}, <No data fields>}, <No data fields>}, <No data fields>}
(gdb)

but this happens fairly quickly. I haven't looked at the code
but it seems we should have detected a failure to allocate memory for
ridx or data.

jwe

Søren Hauberg

2006-06-25 15:43:47 UTC

Permalink

Post by John W. Eaton
| Okay, I'm sorry about the missing information. I'm attaching the
| information from bug_report().
|
| I looked at the code and cond() calls svd(). I don't see a sparse
| implementation of svd() so I'm guessing it's not relevant that the
| matrix is sparse. This problem is propably triggered by the machine
| running out of memory (I only have 512MB). I'm guessing you'll trigger
| the bug on your machine if you increase the m variable.
What LAPACK and BLAS libraries are you using? ATLAS?

I'm using atlas:

ldd `which octave`
linux-gate.so.1 => (0xffffe000)
liboctinterp.so
=> /home/sh/Programmer/lib/octave-2.9.6/liboctinterp.so (0xb7740000)
liboctave.so
=> /home/sh/Programmer/lib/octave-2.9.6/liboctave.so (0xb6f91000)
libcruft.so => /home/sh/Programmer/lib/octave-2.9.6/libcruft.so
(0xb6f3e000)
libumfpack.so.4 => /usr/lib/libumfpack.so.4 (0xb6e87000)
libamd.so.1 => /usr/lib/libamd.so.1 (0xb6e7f000)
liblapack.so.3 => /usr/lib/atlas/liblapack.so.3 (0xb6837000)
libblas.so.3 => /usr/lib/atlas/libblas.so.3 (0xb64f2000)
libfftw3.so.3 => /usr/lib/libfftw3.so.3 (0xb641d000)
libreadline.so.5 => /lib/libreadline.so.5 (0xb63ef000)
libncurses.so.5 => /lib/libncurses.so.5 (0xb63ae000)
libdl.so.2 => /lib/tls/i686/cmov/libdl.so.2 (0xb63ab000)
libhdf5-1.6.4.so.0 => /usr/lib/libhdf5-1.6.4.so.0 (0xb6282000)
libz.so.1 => /usr/lib/libz.so.1 (0xb626e000)
libg2c.so.0 => /usr/lib/libg2c.so.0 (0xb6246000)
libm.so.6 => /lib/tls/i686/cmov/libm.so.6 (0xb6224000)
libgcc_s.so.1 => /lib/libgcc_s.so.1 (0xb621a000)
libstdc++.so.6 => /usr/lib/libstdc++.so.6 (0xb6145000)
libc.so.6 => /lib/tls/i686/cmov/libc.so.6 (0xb6016000)
libpthread.so.0 => /lib/tls/i686/cmov/libpthread.so.0
(0xb6003000)
/lib/ld-linux.so.2 (0xb7f7e000)

Post by John W. Eaton
How much memory does your system have?

I have 512 MB ram and 730 MB swap.

Post by John W. Eaton
octave:1> m = 200;
octave:2> n = m;
octave:3> mn = m*n;
octave:4> A = (spdiag(4*ones(1,mn))

Post by SÃ¸ren Hauberg
- spdiag(ones(1,mn-1), 1)
- spdiag(ones(1,mn-1), -1)
- spdiag(ones(1,mn-m), m)
- spdiag(ones(1,mn-m), -m));

octave:5> cond(A)
Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 46912574002112 (LWP 26342)]
0x00002aaaaba57399 in SparseMatrix::matrix_value (this=<value optimized out>)
at /home/jwe/src/octave/liboctave/dSparse.cc:7789
7789 retval.elem (ridx(i), j) = data (i);
Current language: auto; currently c++
(gdb) p ridx
Cannot access memory at address 0x0
(gdb) p data
Cannot access memory at address 0x0
(gdb) p retval
<MArray2<double>> = {
<Array2<double>> = {
<Array<double>> = {
_vptr.Array = 0x2aaaab5cd750,
rep = 0x181bd30,
dimensions = {
rep = 0x181b680
},
idx = 0x0,
idx_count = 0
}, <No data fields>}, <No data fields>}, <No data fields>}
(gdb)
but this happens fairly quickly. I haven't looked at the code
but it seems we should have detected a failure to allocate memory for
ridx or data.

If I increase m to 200 I get a "error: memory exhausted -- trying to
return to prompt", which is just fine.
I had a quick look at the code, but it didn't take long before I had to
face that I really don't know the codebase. Sorry...

Søren

Post by John W. Eaton
jwe

Andy Adler

2006-06-25 18:59:57 UTC

Permalink

Post by SÃ¸ren Hauberg
I looked at the code and cond() calls svd(). I don't see a sparse
implementation of svd() so I'm guessing it's not relevant that the
matrix is sparse. This problem is propably triggered by the machine
running out of memory (I only have 512MB). I'm guessing you'll trigger
the bug on your machine if you increase the m variable.

Octave will "promote" the sparse matrix to full when it tries
to calculate cond. This is because of the svd, as you saw.

Comparing to Matlab (6.5 and 7.0sp2): matlab
refuses to calculate cond but will calculate condest:

a=sparse(eye(3));

Post by SÃ¸ren Hauberg

cond(a)

Warning: Using CONDEST instead of COND for sparse matrix.

Post by SÃ¸ren Hauberg
In <a href="error:/disks/hda5/opt/matlab7/toolbox/matlab/matfun/cond.m,28,1">cond at 28</a>

ans =
1

The underlying issue is the calculation of norms.
The 1-norm and inf-norm can be calculated for a sparse
matrix in a computationally reasonable way.

To extract the code from norm.m (p is the norm-type)
if (p == 1)
retval = max (sum (abs (x)));
elseif (p == 2)
s = svd (x);
retval = s (1);
elseif (p == Inf)
retval = max (sum (abs (x')));
endif

The condest is based on the 1-norm rather than the 2-norm.

Note that Matlab (6.5 and 7.0sp2) will refuse to calculate
the 2-norm of a sparse matrix

Post by SÃ¸ren Hauberg

norm(a,1)

ans =
1

Post by SÃ¸ren Hauberg

norm(a,inf)

ans =
1

Post by SÃ¸ren Hauberg

norm(a,2)

??? Error using ==> norm
Sparse norm(S,2) is not available.

--
Andy Adler <***@site.uOttawa.ca> 1(613)562-5800x6218

John W. Eaton

2006-07-27 22:13:52 UTC

Permalink

Andy Adler

2006-07-27 23:53:24 UTC

Permalink

I would say no, although perhaps we should give a warning that
2-norms of sparse matries can be very slow.

Also, octave shouldn't crash, of course.

One more idea: I wonder if it would be possible to predict whether
a computation will run out of memory. Then we can bail out earlier,
and not irritate the user by having to wait to not get an answer.
OTOH, I can see how this would be very difficult.

--
Andy Adler

John W. Eaton

2006-07-28 02:36:41 UTC

Permalink

On 27-Jul-2006, Andy Adler wrote:

| I would say no, although perhaps we should give a warning that
| 2-norms of sparse matries can be very slow.

OK, I would accept a patch for this.

| Also, octave shouldn't crash, of course.

Right, it shouldn't crash anyway. Instead, it should throw a
bad_alloc exception and end up back at the prompt. Unless the
allocation is done with malloc in an external library and the bad
allocation is not caught. I still see

| One more idea: I wonder if it would be possible to predict whether
| a computation will run out of memory. Then we can bail out earlier,
| and not irritate the user by having to wait to not get an answer.
| OTOH, I can see how this would be very difficult.

It's not really possible on a multi-user machine. Someone else can
grab memory from the system in the time between your calculation of
what is available and when you allocate the memory. It's just better
to try to allocate and then throw an exception when it fails. But C
sucks and fails to provide a good way to handle out-of-memory
conditions, other than checking after every call to malloc (or
realloc). So we can't properly handle out-of-memory conditions in
external C libraries unless they are carefully written.

BTW, I still see the following and I don't know why it is happening or
how to fix it. I don't really understand the sparse code, so it would
help if someone else who needs this can help debug it.

octave:1> m = 200;
octave:2> n = m;
octave:3> mn = m*n;
octave:4> A = (spdiag(4*ones(1,mn))

Post by SÃ¸ren Hauberg
- spdiag(ones(1,mn-1), 1)
- spdiag(ones(1,mn-1), -1)
- spdiag(ones(1,mn-m), m)
- spdiag(ones(1,mn-m), -m));

octave:5> cond(A)

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 46912589648832 (LWP 15081)]
0x00002aaaaba2b349 in SparseMatrix::matrix_value (this=<value optimized out>)
at /home/jwe/src/octave/liboctave/dSparse.cc:7828
7828 retval.elem (ridx(i), j) = data (i);
Current language: auto; currently c++
(gdb) p ridx
Cannot access memory at address 0x0
(gdb) where
#0 0x00002aaaaba2b349 in SparseMatrix::matrix_value (this=<value optimized out>)
at /home/jwe/src/octave/liboctave/dSparse.cc:7828
#1 0x00002aaaab0c482d in octave_sparse_matrix::matrix_value (this=<value optimized out>)
at /home/jwe/src/octave/src/ov-re-sparse.cc:136
#2 0x00002aaab0eec4f0 in Fsvd (args=<value optimized out>, nargout=1) at /home/jwe/src/octave/src/ov.h:580
#3 0x00002aaaaafef505 in octave_builtin::do_multi_index_op (this=0x14a99d0, nargout=1, args=@0x1804430)
at /home/jwe/src/octave/src/ov-builtin.cc:104
#4 0x00002aaaaafeede6 in octave_builtin::subsref (this=0x14a99d0, type=@0x1852aa8, idx=@0x7fffffefde90,
nargout=1) at /home/jwe/src/octave/src/ov-builtin.cc:54
#5 0x00002aaaaafbc0e7 in octave_value::subsref (this=0x7fffffefdeb0, type=@0x1852aa8, idx=@0x7fffffefde90,
nargout=1) at /home/jwe/src/octave/src/ov.cc:734
#6 0x00002aaaab0e076f in tree_index_expression::rvalue (this=0x1852a70, nargout=1)
at /home/jwe/src/octave/src/pt-idx.cc:352
#7 0x00002aaaab0dfa22 in tree_index_expression::rvalue (this=0x1852a70)
at /home/jwe/src/octave/src/pt-idx.cc:363
#8 0x00002aaaab0cdc82 in tree_simple_assignment::rvalue (this=0x18532d0)
at /home/jwe/src/octave/src/pt-assign.cc:82
#9 0x00002aaaab0ccb9b in tree_simple_assignment::rvalue (this=0x18532d0, nargout=<value optimized out>)
at /home/jwe/src/octave/src/pt-assign.cc:64
#10 0x00002aaaab0f93b4 in tree_statement::eval (this=0x1852a00, silent=<value optimized out>, nargout=0,
in_function_body=false) at /home/jwe/src/octave/src/pt-stmt.cc:133
#11 0x00002aaaab0f9834 in tree_statement_list::eval (this=0x1852090, silent=false, nargout=0)
at /home/jwe/src/octave/src/pt-stmt.cc:190
#12 0x00002aaaab0f6fde in tree_if_clause::eval (this=0x1856140) at /home/jwe/src/octave/src/pt-select.cc:54
#13 0x00002aaaab0f70af in tree_if_command_list::eval (this=0x1850b00)
at /home/jwe/src/octave/src/pt-select.cc:85
#14 0x00002aaaab0f70ef in tree_if_command::eval (this=0x1856b40) at /home/jwe/src/octave/src/pt-select.cc:124
#15 0x00002aaaab0f92db in tree_statement::eval (this=0x1856830, silent=<value optimized out>, nargout=0,
in_function_body=false) at /home/jwe/src/octave/src/pt-stmt.cc:102
#16 0x00002aaaab0f9834 in tree_statement_list::eval (this=0x184c330, silent=false, nargout=0)
at /home/jwe/src/octave/src/pt-stmt.cc:190
---Type <return> to continue, or q <return> to quit---
#17 0x00002aaaab0f6fde in tree_if_clause::eval (this=0x1856bd0) at /home/jwe/src/octave/src/pt-select.cc:54
#18 0x00002aaaab0f70af in tree_if_command_list::eval (this=0x1856bf0)
at /home/jwe/src/octave/src/pt-select.cc:85
#19 0x00002aaaab0f70ef in tree_if_command::eval (this=0x1857020) at /home/jwe/src/octave/src/pt-select.cc:124
#20 0x00002aaaab0f92db in tree_statement::eval (this=0x1857b50, silent=<value optimized out>, nargout=0,
in_function_body=true) at /home/jwe/src/octave/src/pt-stmt.cc:102
#21 0x00002aaaab0f9834 in tree_statement_list::eval (this=0x1857b80, silent=false, nargout=0)
at /home/jwe/src/octave/src/pt-stmt.cc:190
#22 0x00002aaaab00056b in octave_user_function::do_multi_index_op (this=0x14956e8, nargout=0, args=@0x1857950)
at /home/jwe/src/octave/src/ov-usr-fcn.cc:359
#23 0x00002aaaaafff648 in octave_user_function::subsref (this=0x14956e8, type=@0x1627718, idx=@0x7fffffefee40,
nargout=0) at /home/jwe/src/octave/src/ov-usr-fcn.cc:220
#24 0x00002aaaaafbc0e7 in octave_value::subsref (this=0x7fffffefee60, type=@0x1627718, idx=@0x7fffffefee40,
nargout=0) at /home/jwe/src/octave/src/ov.cc:734
#25 0x00002aaaab0e076f in tree_index_expression::rvalue (this=0x16276e0, nargout=0)
at /home/jwe/src/octave/src/pt-idx.cc:352
#26 0x00002aaaab0f93b4 in tree_statement::eval (this=0x162a810, silent=<value optimized out>, nargout=0,
in_function_body=false) at /home/jwe/src/octave/src/pt-stmt.cc:133
#27 0x00002aaaab0f9834 in tree_statement_list::eval (this=0x1624a90, silent=false, nargout=0)
at /home/jwe/src/octave/src/pt-stmt.cc:190
#28 0x00002aaaaaf28a31 in main_loop () at /home/jwe/src/octave/src/toplev.cc:225
#29 0x00002aaaaaec0bc0 in octave_main (argc=3, argv=0x7fffffeff4a8, embedded=0)
at /home/jwe/src/octave/src/octave.cc:764
#30 0x00002aaaaf7c34ca in __libc_start_main () from /lib/libc.so.6
#31 0x000000000040078a in _start () at ../sysdeps/x86_64/elf/start.S:113

jwe

Thomas Weber

2006-06-25 16:17:06 UTC

Permalink

Hi,

Post by SÃ¸ren Hauberg
*** glibc detected *** double free or corruption (out): 0x09054be0 ***
panic: Aborted -- stopping myself...
attempting to save variables to `octave-core'...
save to `octave-core' complete
Afbrudt (SIGABRT)

Do you have Octave-forge installed? We had similar reports for the
sparse stuff in octave-forge, compiled against Octave 2.1, e.g.

http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=369545

Thomas

Søren Hauberg

2006-06-25 17:02:21 UTC

Permalink

Post by Thomas Weber
Do you have Octave-forge installed? We had similar reports for the
sparse stuff in octave-forge, compiled against Octave 2.1, e.g.
http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=369545

No octave-forge is installed.

Thanks,
Søren