pub struct SparseLu { /* private fields */ }Expand description
Sparse LU factorisation P A = L U with true row partial pivoting.
Implementations§
Source§impl SparseLu
impl SparseLu
Sourcepub fn perm(&self) -> &[usize]
pub fn perm(&self) -> &[usize]
Get the permutation vector (perm[i] = original row index at position i).
Sourcepub fn l_rows(&self) -> &[Vec<(usize, f64)>]
pub fn l_rows(&self) -> &[Vec<(usize, f64)>]
Get L factor rows (strict lower triangle, unit diagonal implicit).
Sourcepub fn u_rows(&self) -> &[Vec<(usize, f64)>]
pub fn u_rows(&self) -> &[Vec<(usize, f64)>]
Get U factor rows (upper triangle including diagonal).
Sourcepub fn verify_pa_eq_lu(&self, a: &SparseMatrix) -> f64
pub fn verify_pa_eq_lu(&self, a: &SparseMatrix) -> f64
Verify PA = LU for debugging purposes. Returns max absolute difference between PA and LU.
Examples found in repository?
examples/sparse_lu_test.rs (line 18)
4fn main() {
5 // Test 1: Simple 2x2 matrix with zero diagonal
6 println!("Test 1: 2x2 matrix [[0, 1], [1, 0]]");
7 let mut a = SparseMatrix::new(2);
8 a.add(0, 1, 1.0);
9 a.add(1, 0, 1.0);
10 a.compress();
11 let lu = SparseLu::factor(&a).unwrap();
12 let b = vec![1.0, 2.0];
13 let x = lu.solve(&b);
14 println!(" Solution: {:?}", x);
15 println!(" Expected: [2, 1]");
16
17 // Verify PA = LU
18 let max_diff = lu.verify_pa_eq_lu(&a);
19 println!(" max|PA - LU| = {:.2e}", max_diff);
20 assert!(max_diff < 1e-12, "PA != LU: max_diff = {}", max_diff);
21
22 // Test 2: Diagonally dominant
23 println!("\nTest 2: Diagonally dominant 3x3");
24 let mut a2 = SparseMatrix::new(3);
25 a2.add(0, 0, 4.0);
26 a2.add(0, 1, 1.0);
27 a2.add(1, 0, 1.0);
28 a2.add(1, 1, 4.0);
29 a2.add(1, 2, 1.0);
30 a2.add(2, 1, 1.0);
31 a2.add(2, 2, 4.0);
32 a2.compress();
33 let lu2 = SparseLu::factor(&a2).unwrap();
34 let b2 = vec![1.0, 2.0, 3.0];
35 let x2 = lu2.solve(&b2);
36 println!(" Solution: {:?}", x2);
37
38 let max_diff2 = lu2.verify_pa_eq_lu(&a2);
39 println!(" max|PA - LU| = {:.2e}", max_diff2);
40 assert!(max_diff2 < 1e-12, "PA != LU: max_diff = {}", max_diff2);
41
42 // Test 3: Zero diagonal with pivoting needed
43 println!("\nTest 3: [[1, 2], [1e-14, 1]] - needs pivoting");
44 let mut a3 = SparseMatrix::new(2);
45 a3.add(0, 0, 1.0);
46 a3.add(0, 1, 2.0);
47 a3.add(1, 0, 1e-14);
48 a3.add(1, 1, 1.0);
49 a3.compress();
50 match SparseLu::factor(&a3) {
51 Ok(lu) => {
52 let b3 = vec![1.0, 2.0];
53 let x3 = lu.solve(&b3);
54 println!(" Solution: {:?}", x3);
55 }
56 Err(e) => {
57 println!(" Error: {}", e);
58 }
59 }
60
61 println!("\nAll tests passed!");
62}More examples
examples/test_augmented_solve.rs (line 44)
15fn main() {
16 // Load the exact augmented system for Angle_100x100 (the one that fails)
17 let data = load_json("rust_augmented_Angle_100x100.json");
18
19 let n_dof = data["n_dof"].as_u64().unwrap() as usize;
20 let A_data = &data["A"];
21 let b: Vec<f64> = serde_json::from_value(data["b"].clone()).unwrap();
22
23 // Build sparse matrix
24 let mut A = SparseMatrix::new(n_dof + 1);
25 let rows: Vec<usize> = serde_json::from_value(A_data["row"].clone()).unwrap();
26 let cols: Vec<usize> = serde_json::from_value(A_data["col"].clone()).unwrap();
27 let data: Vec<f64> = serde_json::from_value(A_data["data"].clone()).unwrap();
28 for ((r, c), v) in rows.into_iter().zip(cols).zip(data) {
29 A.add(r, c, v);
30 }
31 A.compress();
32
33 println!(
34 "Matrix size: {}x{}, nnz: {}",
35 n_dof + 1,
36 n_dof + 1,
37 A_data["data"].as_array().unwrap().len()
38 );
39
40 // Try SparseLU
41 let lu = SparseLu::factor(&A).unwrap();
42
43 // Verify PA = LU
44 let max_diff = lu.verify_pa_eq_lu(&A);
45 println!("max|PA - LU| = {:.2e}", max_diff);
46
47 let x = lu.solve(&b).unwrap();
48
49 println!("Solution x (first 10): {:?}", &x[..10.min(x.len())]);
50 println!("x len: {}", x.len());
51 println!("Last element (lambda): {}", x.last().unwrap());
52
53 // Check if PA = LU holds
54 let max_diff = lu.verify_pa_eq_lu(&A);
55 println!("max|PA - LU| = {:.2e}", max_diff);
56
57 // Compute residual
58 let n = A.n;
59 let mut res = vec![0.0; n];
60 let (rows, cols, vals) = A.triplets();
61 for (&i, (&j, &v)) in rows.iter().zip(cols.iter().zip(vals.iter())) {
62 res[i] += v * x[j];
63 }
64
65 let max_res = res
66 .iter()
67 .zip(b.iter())
68 .map(|(&r, &b)| (r - b).abs())
69 .fold(0.0, f64::max);
70 let b_norm = b.iter().map(|&v| v.abs()).fold(0.0, f64::max);
71 println!(
72 "Max residual: {:.2e}, rel: {:.2e}",
73 max_res,
74 max_res / b_norm.max(1e-300)
75 );
76
77 // Check constraint residual C^T * omega
78 let c_data: Vec<f64> =
79 serde_json::from_value(load_json("rust_augmented_Angle_100x100.json")["C"].clone())
80 .unwrap();
81 let omega = &x[..x.len() - 1];
82 let ct_omega: f64 = c_data
83 .iter()
84 .zip(x.iter().take(n_dof))
85 .map(|(&c, &w)| c * w)
86 .sum();
87 println!("C^T * omega: {:.2e}", ct_omega);
88 println!("Lambda: {:.2e}", x.last().unwrap());
89}Sourcepub fn factor(a: &SparseMatrix) -> Result<SparseLu, String>
pub fn factor(a: &SparseMatrix) -> Result<SparseLu, String>
Factor A with true row partial pivoting (PA = LU). Returns error if matrix is singular or nearly singular.
Examples found in repository?
examples/test_sparse_lu.rs (line 11)
4fn main() {
5 // Test 1: Simple 2x2 matrix
6 println!("Test 1: 2x2 matrix [[0, 1], [1, 0]]");
7 let mut a = SparseMatrix::new(2);
8 a.add(0, 1, 1.0);
9 a.add(1, 0, 1.0);
10 a.compress();
11 let lu = SparseLu::factor(&a).unwrap();
12 let b = vec![1.0, 2.0];
13 let x = lu.solve(&b);
14 println!(" Solution: {:?}", x);
15 println!(" Expected: [2, 1]");
16
17 // Test 2: Diagonally dominant
18 println!("\nTest 2: Diagonally dominant");
19 let mut a2 = SparseMatrix::new(3);
20 a2.add(0, 0, 4.0);
21 a2.add(0, 1, 1.0);
22 a2.add(1, 0, 1.0);
23 a2.add(1, 1, 4.0);
24 a2.add(1, 2, 1.0);
25 a2.add(2, 1, 1.0);
26 a2.add(2, 2, 4.0);
27 a2.compress();
28 let lu2 = SparseLu::factor(&a2).unwrap();
29 let b2 = vec![1.0, 2.0, 3.0];
30 let x2 = lu2.solve(&b2);
31 println!(" Solution: {:?}", x2);
32
33 // Verify
34 let mut a2_dense = vec![vec![0.0; 3]; 3];
35 for i in 0..3 {
36 for j in 0..3 {
37 // Reconstruct from factors
38 }
39 }
40}More examples
examples/sparse_lu_test.rs (line 11)
4fn main() {
5 // Test 1: Simple 2x2 matrix with zero diagonal
6 println!("Test 1: 2x2 matrix [[0, 1], [1, 0]]");
7 let mut a = SparseMatrix::new(2);
8 a.add(0, 1, 1.0);
9 a.add(1, 0, 1.0);
10 a.compress();
11 let lu = SparseLu::factor(&a).unwrap();
12 let b = vec![1.0, 2.0];
13 let x = lu.solve(&b);
14 println!(" Solution: {:?}", x);
15 println!(" Expected: [2, 1]");
16
17 // Verify PA = LU
18 let max_diff = lu.verify_pa_eq_lu(&a);
19 println!(" max|PA - LU| = {:.2e}", max_diff);
20 assert!(max_diff < 1e-12, "PA != LU: max_diff = {}", max_diff);
21
22 // Test 2: Diagonally dominant
23 println!("\nTest 2: Diagonally dominant 3x3");
24 let mut a2 = SparseMatrix::new(3);
25 a2.add(0, 0, 4.0);
26 a2.add(0, 1, 1.0);
27 a2.add(1, 0, 1.0);
28 a2.add(1, 1, 4.0);
29 a2.add(1, 2, 1.0);
30 a2.add(2, 1, 1.0);
31 a2.add(2, 2, 4.0);
32 a2.compress();
33 let lu2 = SparseLu::factor(&a2).unwrap();
34 let b2 = vec![1.0, 2.0, 3.0];
35 let x2 = lu2.solve(&b2);
36 println!(" Solution: {:?}", x2);
37
38 let max_diff2 = lu2.verify_pa_eq_lu(&a2);
39 println!(" max|PA - LU| = {:.2e}", max_diff2);
40 assert!(max_diff2 < 1e-12, "PA != LU: max_diff = {}", max_diff2);
41
42 // Test 3: Zero diagonal with pivoting needed
43 println!("\nTest 3: [[1, 2], [1e-14, 1]] - needs pivoting");
44 let mut a3 = SparseMatrix::new(2);
45 a3.add(0, 0, 1.0);
46 a3.add(0, 1, 2.0);
47 a3.add(1, 0, 1e-14);
48 a3.add(1, 1, 1.0);
49 a3.compress();
50 match SparseLu::factor(&a3) {
51 Ok(lu) => {
52 let b3 = vec![1.0, 2.0];
53 let x3 = lu.solve(&b3);
54 println!(" Solution: {:?}", x3);
55 }
56 Err(e) => {
57 println!(" Error: {}", e);
58 }
59 }
60
61 println!("\nAll tests passed!");
62}examples/test_augmented_solve.rs (line 41)
15fn main() {
16 // Load the exact augmented system for Angle_100x100 (the one that fails)
17 let data = load_json("rust_augmented_Angle_100x100.json");
18
19 let n_dof = data["n_dof"].as_u64().unwrap() as usize;
20 let A_data = &data["A"];
21 let b: Vec<f64> = serde_json::from_value(data["b"].clone()).unwrap();
22
23 // Build sparse matrix
24 let mut A = SparseMatrix::new(n_dof + 1);
25 let rows: Vec<usize> = serde_json::from_value(A_data["row"].clone()).unwrap();
26 let cols: Vec<usize> = serde_json::from_value(A_data["col"].clone()).unwrap();
27 let data: Vec<f64> = serde_json::from_value(A_data["data"].clone()).unwrap();
28 for ((r, c), v) in rows.into_iter().zip(cols).zip(data) {
29 A.add(r, c, v);
30 }
31 A.compress();
32
33 println!(
34 "Matrix size: {}x{}, nnz: {}",
35 n_dof + 1,
36 n_dof + 1,
37 A_data["data"].as_array().unwrap().len()
38 );
39
40 // Try SparseLU
41 let lu = SparseLu::factor(&A).unwrap();
42
43 // Verify PA = LU
44 let max_diff = lu.verify_pa_eq_lu(&A);
45 println!("max|PA - LU| = {:.2e}", max_diff);
46
47 let x = lu.solve(&b).unwrap();
48
49 println!("Solution x (first 10): {:?}", &x[..10.min(x.len())]);
50 println!("x len: {}", x.len());
51 println!("Last element (lambda): {}", x.last().unwrap());
52
53 // Check if PA = LU holds
54 let max_diff = lu.verify_pa_eq_lu(&A);
55 println!("max|PA - LU| = {:.2e}", max_diff);
56
57 // Compute residual
58 let n = A.n;
59 let mut res = vec![0.0; n];
60 let (rows, cols, vals) = A.triplets();
61 for (&i, (&j, &v)) in rows.iter().zip(cols.iter().zip(vals.iter())) {
62 res[i] += v * x[j];
63 }
64
65 let max_res = res
66 .iter()
67 .zip(b.iter())
68 .map(|(&r, &b)| (r - b).abs())
69 .fold(0.0, f64::max);
70 let b_norm = b.iter().map(|&v| v.abs()).fold(0.0, f64::max);
71 println!(
72 "Max residual: {:.2e}, rel: {:.2e}",
73 max_res,
74 max_res / b_norm.max(1e-300)
75 );
76
77 // Check constraint residual C^T * omega
78 let c_data: Vec<f64> =
79 serde_json::from_value(load_json("rust_augmented_Angle_100x100.json")["C"].clone())
80 .unwrap();
81 let omega = &x[..x.len() - 1];
82 let ct_omega: f64 = c_data
83 .iter()
84 .zip(x.iter().take(n_dof))
85 .map(|(&c, &w)| c * w)
86 .sum();
87 println!("C^T * omega: {:.2e}", ct_omega);
88 println!("Lambda: {:.2e}", x.last().unwrap());
89}Sourcepub fn solve(&self, b: &[f64]) -> Result<Vec<f64>, String>
pub fn solve(&self, b: &[f64]) -> Result<Vec<f64>, String>
Solve A x = b via forward/back substitution using P A = L U. Returns x = A^{-1} b or error if diagonal is near-zero.
Examples found in repository?
examples/test_sparse_lu.rs (line 13)
4fn main() {
5 // Test 1: Simple 2x2 matrix
6 println!("Test 1: 2x2 matrix [[0, 1], [1, 0]]");
7 let mut a = SparseMatrix::new(2);
8 a.add(0, 1, 1.0);
9 a.add(1, 0, 1.0);
10 a.compress();
11 let lu = SparseLu::factor(&a).unwrap();
12 let b = vec![1.0, 2.0];
13 let x = lu.solve(&b);
14 println!(" Solution: {:?}", x);
15 println!(" Expected: [2, 1]");
16
17 // Test 2: Diagonally dominant
18 println!("\nTest 2: Diagonally dominant");
19 let mut a2 = SparseMatrix::new(3);
20 a2.add(0, 0, 4.0);
21 a2.add(0, 1, 1.0);
22 a2.add(1, 0, 1.0);
23 a2.add(1, 1, 4.0);
24 a2.add(1, 2, 1.0);
25 a2.add(2, 1, 1.0);
26 a2.add(2, 2, 4.0);
27 a2.compress();
28 let lu2 = SparseLu::factor(&a2).unwrap();
29 let b2 = vec![1.0, 2.0, 3.0];
30 let x2 = lu2.solve(&b2);
31 println!(" Solution: {:?}", x2);
32
33 // Verify
34 let mut a2_dense = vec![vec![0.0; 3]; 3];
35 for i in 0..3 {
36 for j in 0..3 {
37 // Reconstruct from factors
38 }
39 }
40}More examples
examples/sparse_lu_test.rs (line 13)
4fn main() {
5 // Test 1: Simple 2x2 matrix with zero diagonal
6 println!("Test 1: 2x2 matrix [[0, 1], [1, 0]]");
7 let mut a = SparseMatrix::new(2);
8 a.add(0, 1, 1.0);
9 a.add(1, 0, 1.0);
10 a.compress();
11 let lu = SparseLu::factor(&a).unwrap();
12 let b = vec![1.0, 2.0];
13 let x = lu.solve(&b);
14 println!(" Solution: {:?}", x);
15 println!(" Expected: [2, 1]");
16
17 // Verify PA = LU
18 let max_diff = lu.verify_pa_eq_lu(&a);
19 println!(" max|PA - LU| = {:.2e}", max_diff);
20 assert!(max_diff < 1e-12, "PA != LU: max_diff = {}", max_diff);
21
22 // Test 2: Diagonally dominant
23 println!("\nTest 2: Diagonally dominant 3x3");
24 let mut a2 = SparseMatrix::new(3);
25 a2.add(0, 0, 4.0);
26 a2.add(0, 1, 1.0);
27 a2.add(1, 0, 1.0);
28 a2.add(1, 1, 4.0);
29 a2.add(1, 2, 1.0);
30 a2.add(2, 1, 1.0);
31 a2.add(2, 2, 4.0);
32 a2.compress();
33 let lu2 = SparseLu::factor(&a2).unwrap();
34 let b2 = vec![1.0, 2.0, 3.0];
35 let x2 = lu2.solve(&b2);
36 println!(" Solution: {:?}", x2);
37
38 let max_diff2 = lu2.verify_pa_eq_lu(&a2);
39 println!(" max|PA - LU| = {:.2e}", max_diff2);
40 assert!(max_diff2 < 1e-12, "PA != LU: max_diff = {}", max_diff2);
41
42 // Test 3: Zero diagonal with pivoting needed
43 println!("\nTest 3: [[1, 2], [1e-14, 1]] - needs pivoting");
44 let mut a3 = SparseMatrix::new(2);
45 a3.add(0, 0, 1.0);
46 a3.add(0, 1, 2.0);
47 a3.add(1, 0, 1e-14);
48 a3.add(1, 1, 1.0);
49 a3.compress();
50 match SparseLu::factor(&a3) {
51 Ok(lu) => {
52 let b3 = vec![1.0, 2.0];
53 let x3 = lu.solve(&b3);
54 println!(" Solution: {:?}", x3);
55 }
56 Err(e) => {
57 println!(" Error: {}", e);
58 }
59 }
60
61 println!("\nAll tests passed!");
62}examples/test_augmented_solve.rs (line 47)
15fn main() {
16 // Load the exact augmented system for Angle_100x100 (the one that fails)
17 let data = load_json("rust_augmented_Angle_100x100.json");
18
19 let n_dof = data["n_dof"].as_u64().unwrap() as usize;
20 let A_data = &data["A"];
21 let b: Vec<f64> = serde_json::from_value(data["b"].clone()).unwrap();
22
23 // Build sparse matrix
24 let mut A = SparseMatrix::new(n_dof + 1);
25 let rows: Vec<usize> = serde_json::from_value(A_data["row"].clone()).unwrap();
26 let cols: Vec<usize> = serde_json::from_value(A_data["col"].clone()).unwrap();
27 let data: Vec<f64> = serde_json::from_value(A_data["data"].clone()).unwrap();
28 for ((r, c), v) in rows.into_iter().zip(cols).zip(data) {
29 A.add(r, c, v);
30 }
31 A.compress();
32
33 println!(
34 "Matrix size: {}x{}, nnz: {}",
35 n_dof + 1,
36 n_dof + 1,
37 A_data["data"].as_array().unwrap().len()
38 );
39
40 // Try SparseLU
41 let lu = SparseLu::factor(&A).unwrap();
42
43 // Verify PA = LU
44 let max_diff = lu.verify_pa_eq_lu(&A);
45 println!("max|PA - LU| = {:.2e}", max_diff);
46
47 let x = lu.solve(&b).unwrap();
48
49 println!("Solution x (first 10): {:?}", &x[..10.min(x.len())]);
50 println!("x len: {}", x.len());
51 println!("Last element (lambda): {}", x.last().unwrap());
52
53 // Check if PA = LU holds
54 let max_diff = lu.verify_pa_eq_lu(&A);
55 println!("max|PA - LU| = {:.2e}", max_diff);
56
57 // Compute residual
58 let n = A.n;
59 let mut res = vec![0.0; n];
60 let (rows, cols, vals) = A.triplets();
61 for (&i, (&j, &v)) in rows.iter().zip(cols.iter().zip(vals.iter())) {
62 res[i] += v * x[j];
63 }
64
65 let max_res = res
66 .iter()
67 .zip(b.iter())
68 .map(|(&r, &b)| (r - b).abs())
69 .fold(0.0, f64::max);
70 let b_norm = b.iter().map(|&v| v.abs()).fold(0.0, f64::max);
71 println!(
72 "Max residual: {:.2e}, rel: {:.2e}",
73 max_res,
74 max_res / b_norm.max(1e-300)
75 );
76
77 // Check constraint residual C^T * omega
78 let c_data: Vec<f64> =
79 serde_json::from_value(load_json("rust_augmented_Angle_100x100.json")["C"].clone())
80 .unwrap();
81 let omega = &x[..x.len() - 1];
82 let ct_omega: f64 = c_data
83 .iter()
84 .zip(x.iter().take(n_dof))
85 .map(|(&c, &w)| c * w)
86 .sum();
87 println!("C^T * omega: {:.2e}", ct_omega);
88 println!("Lambda: {:.2e}", x.last().unwrap());
89}Auto Trait Implementations§
impl Freeze for SparseLu
impl RefUnwindSafe for SparseLu
impl Send for SparseLu
impl Sync for SparseLu
impl Unpin for SparseLu
impl UnsafeUnpin for SparseLu
impl UnwindSafe for SparseLu
Blanket Implementations§
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more