BUG: thread 'main' panicked - called `ColShared3::prev()` on a `HeadHash` value: X

matospiso commented 9 months ago

Hello, I'd like to use your code for an application in recommender systems, which currently computes colamd through cholmod using a Python wrapper (https://scikit-sparse.readthedocs.io/en/latest/) - and I would like to get rid of this dependency and use your code instead. However, I stumbled upon several cases where the algorithm panics on valid input. Could you help me solve it? 🙂

Disclaimer: I'm very new to Rust and can't debug this on my own. It's possible I made a mistake somewhere in my Rust code, please be patient.

Problem

colamd panics on valid input -- symbolic sparse matrix, even a small one.

I created 3 small test cases:

Matrix 100 is a 100x100 submatrix of matrix 101. 101 is a 101x101 submatrix of matrix 120. Matrix 120 has shape 120x120, and is a submatrix of a large sparse matrix (see section Data)
colamd runs fine for matrix 100
panics for matrices 101 and 120 (see console outputs)

How to run

recreate the folder structure, put data in correct folders (see File structure)
from project root (rust_colamd), run cargo build
cargo run

To see outputs for matrix 101, uncomment the line in main()

Console outputs

100x100 matrix

Reading data/100/shape.txt
Reading data/100/indices.txt
Reading data/100/indptr.txt
Matrix stats:

n rows: 100
n cols: 100
indptr range: 0 - 1302
indices range: 0 - 99
nnz: 1302

recommended length: 2964
time elapsed (data preparation): 0 ms

Running colamd with arguments:
n_row 100
n_col 100
a_len 2964
len(a_i) 2964
len(p) 101

colamd result: true
time elapsed (colamd): 0 ms

101x101 matrix

Reading data/101/shape.txt
Reading data/101/indices.txt
Reading data/101/indptr.txt
Matrix stats:

n rows: 101
n cols: 101
indptr range: 0 - 1315
indices range: 0 - 100
nnz: 1315

recommended length: 2994
time elapsed (data preparation): 0 ms

Running colamd with arguments:
n_row 101
n_col 101
a_len 2994
len(a_i) 2994
len(p) 102

thread 'main' panicked at /Users/masp/.cargo/registry/src/index.crates.io-6f17d22bba15001f/colamd-0.1.0/src/col.rs:134:17:
called `ColShared3::prev()` on a `HeadHash` value: -1
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

120x120 matrix

Reading data/120/shape.txt
Reading data/120/indices.txt
Reading data/120/indptr.txt
Matrix stats:

n rows: 120
n cols: 120
indptr range: 0 - 1731
indices range: 0 - 119
nnz: 1731

recommended length: 3928
time elapsed (data preparation): 0 ms

Running colamd with arguments:
n_row 120
n_col 120
a_len 3928
len(a_i) 3928
len(p) 121

thread 'main' panicked at /Users/masp/.cargo/registry/src/index.crates.io-6f17d22bba15001f/colamd-0.1.0/src/col.rs:134:17:
called `ColShared3::prev()` on a `HeadHash` value: 3
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Reproducing the issue

Rust version

$ rustc --version
rustc 1.75.0 (82e1608df 2023-12-21)

File structure

rust_colamd
|    Cargo.toml
|___ src
|         main.rs
|___ data
     |___ 100
     |       indices.txt
     |       indptr.txt
     |       shape.txt
     |___ 101
     |       indices.txt
     |       indptr.txt
     |       shape.txt
     |___ 120
             indices.txt
             indptr.txt
             shape.txt

Data

data.zip
parts of a sparse user-item matrix (the full matrix is obtained from ratings.csv in this dataset)
3 submatrices (100x100, 101x101, 120x120)
indices ... row indices (0 to n_row - 1)
indptr ... n_col + 1 values (0 to nnz)
shape ... shape of matrix

Running colamd on the full matrix also panics, that's how I initially found out, but I created some smaller submatrices to demonstrate the issue.

`Cargo.toml`

[package]
name = "rust_colamd"
version = "0.1.0"
edition = "2021"

[dependencies]
colamd = "0.1.0"

`main.rs`

use std::fs::File;
use std::io::prelude::*;
use std::path::Path;
use std::time::Instant;
use colamd;

struct SymbolicCSC {
    n_row: i32,
    n_col: i32,
    indices: Vec<i32>,
    indptr: Vec<i32>,
}

fn read_vector_from_file(filename: &str) -> Vec<i32> {
    let path = Path::new(filename);
    let mut file = match File::open(&path) {
        Err(why) => panic!("couldn't open {}: {}", path.display(), why),
        Ok(file) => file,
    };
    println!("Reading {}", path.display());
    let mut s = String::new();
    match file.read_to_string(&mut s) {
        Err(why) => panic!("couldn't read {}: {}", path.display(), why),
        Ok(_) => ()
    };
    let numbers: Vec<i32> = s.trim().split("\n").map(|x| x.parse::<i32>().unwrap()).collect();
    return numbers;
}

fn run_colamd(matrix: &str) {
    let shape_filename = format!("data/{matrix}/shape.txt");
    let shape: Vec<i32> = read_vector_from_file(&shape_filename);

    let indices_filename = format!("data/{matrix}/indices.txt");
    let indices: Vec<i32> = read_vector_from_file(&indices_filename);

    let indptr_filename = format!("data/{matrix}/indptr.txt");
    let indptr: Vec<i32> = read_vector_from_file(&indptr_filename);

    let csc_matrix = SymbolicCSC{
        n_row: shape[0],
        n_col: shape[1],
        indices: indices,
        indptr: indptr,
    };

    let nnz = csc_matrix.indices.len();
    println!("Matrix stats:");
    println!("\nn rows: {}", csc_matrix.n_row);
    println!("n cols: {}", csc_matrix.n_col);
    println!("indptr range: {} - {}", csc_matrix.indptr.iter().min().unwrap_or(&0), csc_matrix.indptr.iter().max().unwrap_or(&0));
    println!("indices range: {} - {}", csc_matrix.indices.iter().min().unwrap_or(&0), csc_matrix.indices.iter().max().unwrap_or(&0));
    println!("nnz: {}\n", nnz);

    let rec_a_len: usize = colamd::recommended(nnz as i32, csc_matrix.n_row, csc_matrix.n_col) as usize;
    println!("recommended length: {}", rec_a_len);

    let mut a_i = csc_matrix.indices;
    let empty = vec![0; rec_a_len - nnz];
    a_i = [&a_i[..], &empty[..]].concat();
    let mut p = csc_matrix.indptr;
    let mut stats: [i32; 20] = [0; 20];

    let now = Instant::now();
    println!("Running colamd with arguments:");
    println!("n_row {:?}", csc_matrix.n_row);
    println!("n_col {:?}", csc_matrix.n_col);
    println!("a_len {:?}", rec_a_len as i32);
    println!("len(a_i) {:?}", a_i.len());
    println!("len(p) {:?}\n", p.len());

    let knobs = colamd::default_knobs();
    let colamd_result = colamd::colamd(csc_matrix.n_row, csc_matrix.n_col, rec_a_len as i32, &mut a_i, &mut p, Some(knobs), &mut stats);
    println!("colamd result: {:?}", colamd_result);
    let elapsed_time = now.elapsed();
    println!("time elapsed (colamd): {:?} ms\n", elapsed_time.as_millis());
}

fn main() {
    run_colamd("100");
    println!("---------------------------");
    // run_colamd("101");
    println!("---------------------------");
    run_colamd("120");
}

rwl commented 9 months ago

Have you tried AMD? It is better tested and should drop in quite easily. For my work it typically works better than COLAMD.

https://crates.io/crates/amd

Alternatively, you could try using the C version of COLAMD from Rust. This would show if the issue is with my translation of the union fields.

https://crates.io/crates/suitesparse_sys https://github.com/rwl/spsolve/blob/main/src/lufact.rs#L48

matospiso commented 9 months ago

Hi, thank you for your response. For the purposes of my project I wrote simple Python bindings for the official C implementation of COLAMD, and it's working fine even on inputs where the Rust code panics. Consequently, the bug is most likely in the translation.

rwl / colamd_rs