nalgebra-sparse-linalg 0.1.10

Sparse linear algebra library for Rust using nalgebra including linear solvers and SVD.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

use super::{*, graph::strength_graph};

#[derive(Clone, Copy, PartialEq, Eq)]
pub(crate) enum Mark {
    Unmarked,
    C, // High degree
    F, //High neighbor 
}

#[derive(Clone)]
struct Node {
    index: usize,
    degree: usize,
}

pub(crate) fn coarsen<T>(a: &CsrMatrix<T>, theta: T) -> (Vec<Mark>, Vec<usize>)
where 
    T: RealField + Copy,
{
    let n = a.nrows();
    let graph = strength_graph(a, theta);
    
    // Create nodes with degrees in one pass, avoiding indexing
    let mut nodes: Vec<Node> = graph.iter()
        .enumerate()
        .map(|(index, neighbors)| Node {
            index,
            degree: neighbors.len(),
        })
        .collect();

    // Sort by degree (descending) - this is the correct order for Ruge-Stüben
    nodes.sort_unstable_by(|a, b| b.degree.cmp(&a.degree));
    
    // Pre-allocate marking vectors
    let mut marks = vec![Mark::Unmarked; n];
    let mut coarse_of = vec![usize::MAX; n];
    let mut next_coarse = 0usize;

    // Ruge-Stüben coarsening algorithm
    for node in &nodes {
        if marks[node.index] != Mark::Unmarked {
            continue;
        }
        
        // Mark the node as C (coarse)
        marks[node.index] = Mark::C;
        coarse_of[node.index] = next_coarse;
        next_coarse += 1;
        
        // Mark all strong neighbors as F (fine)
        for &neighbor in &graph[node.index] {
            if matches!(marks[neighbor], Mark::Unmarked) {
                marks[neighbor] = Mark::F;
            }
        }
    }
    
    (marks, coarse_of)
}