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

[matospiso]

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

1. recreate the folder structure, put data in correct folders (see File structure)
2. from project root (rust_colamd), run cargo build
3. 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]

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]

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.