use super::structure::validate_csr_parts;
use super::views::{CsrRow, CsrView};
use crate::domain::real::RealScalar;
use crate::domain::scalar::Scalar;
use eunomia::FloatElement;
use leto::{Array2, ArrayView2, LetoError, Result};
#[derive(Debug, Clone, PartialEq)]
pub struct CsrMatrix<T> {
values: Vec<T>,
col_indices: Vec<usize>,
row_ptr: Vec<usize>,
nrows: usize,
ncols: usize,
}
impl<T: Scalar> CsrMatrix<T> {
#[must_use = "from_dense returns the compressed matrix"]
pub fn from_dense(matrix: &ArrayView2<'_, T>) -> Self {
let [nrows, ncols] = matrix.shape();
let mut values = Vec::new();
let mut col_indices = Vec::new();
let mut row_ptr = Vec::with_capacity(nrows + 1);
row_ptr.push(0);
if let Some(dense) = matrix.as_slice() {
for i in 0..nrows {
let row = &dense[i * ncols..i * ncols + ncols];
for (j, &value) in row.iter().enumerate() {
if value != T::ZERO {
values.push(value);
col_indices.push(j);
}
}
row_ptr.push(values.len());
}
} else {
let strides = matrix.strides();
let data = matrix.data();
for i in 0..nrows {
if ncols == 0 {
row_ptr.push(values.len());
continue;
}
let mut offset = matrix
.layout()
.offset_of([i, 0])
.expect("row start is in bounds") as isize;
for j in 0..ncols {
let value = data[offset as usize];
if value != T::ZERO {
values.push(value);
col_indices.push(j);
}
offset += strides[1];
}
row_ptr.push(values.len());
}
}
Self {
values,
col_indices,
row_ptr,
nrows,
ncols,
}
}
pub fn from_parts(
values: Vec<T>,
col_indices: Vec<usize>,
row_ptr: Vec<usize>,
nrows: usize,
ncols: usize,
) -> Result<Self> {
validate_csr_parts(values.len(), &col_indices, &row_ptr, nrows, ncols)?;
Ok(Self {
values,
col_indices,
row_ptr,
nrows,
ncols,
})
}
#[must_use]
#[inline]
pub fn shape(&self) -> (usize, usize) {
(self.nrows, self.ncols)
}
#[must_use]
#[inline]
pub fn nnz(&self) -> usize {
self.values.len()
}
#[must_use]
#[inline]
pub fn nrows(&self) -> usize {
self.nrows
}
#[must_use]
#[inline]
pub fn ncols(&self) -> usize {
self.ncols
}
#[must_use]
#[inline]
pub fn density(&self) -> f64 {
let total = self.nrows * self.ncols;
if total == 0 {
0.0
} else {
self.nnz() as f64 / total as f64
}
}
#[must_use]
#[inline]
pub fn as_parts(&self) -> (&[T], &[usize], &[usize]) {
(&self.values, &self.col_indices, &self.row_ptr)
}
#[must_use]
#[inline]
pub fn as_parts_mut(&mut self) -> (&mut [T], &[usize], &[usize]) {
(&mut self.values, &self.col_indices, &self.row_ptr)
}
#[must_use]
#[inline]
pub fn as_view(&self) -> CsrView<'_, T> {
CsrView {
values: &self.values,
col_indices: &self.col_indices,
row_ptr: &self.row_ptr,
nrows: self.nrows,
ncols: self.ncols,
}
}
#[must_use]
#[inline]
pub fn row_ptr(&self) -> &[usize] {
&self.row_ptr
}
#[must_use]
#[inline]
pub fn col_indices(&self) -> &[usize] {
&self.col_indices
}
#[must_use]
#[inline]
pub fn values(&self) -> &[T] {
&self.values
}
#[must_use]
#[inline]
pub fn row(&self, row: usize) -> CsrRow<'_, T> {
let start = self.row_ptr[row];
let end = self.row_ptr[row + 1];
CsrRow {
col_indices: &self.col_indices[start..end],
values: &self.values[start..end],
}
}
#[must_use]
#[inline]
pub fn get(&self, row: usize, col: usize) -> Option<T> {
let r = self.row(row);
r.col_indices
.binary_search(&col)
.ok()
.map(|pos| r.values[pos])
}
#[must_use]
pub fn diagonal(&self) -> Vec<T> {
let mut diag = vec![T::ZERO; self.nrows];
for (row, d) in diag.iter_mut().enumerate().take(self.nrows) {
for p in self.row_ptr[row]..self.row_ptr[row + 1] {
if self.col_indices[p] == row {
*d = self.values[p];
break;
}
}
}
diag
}
#[must_use = "zeros returns the constructed sparse matrix"]
pub fn zeros(nrows: usize, ncols: usize) -> Self {
Self {
values: Vec::new(),
col_indices: Vec::new(),
row_ptr: vec![0; nrows.saturating_add(1)],
nrows,
ncols,
}
}
#[must_use]
#[inline]
pub fn values_mut(&mut self) -> &mut [T] {
&mut self.values
}
pub fn scale_values(&mut self, factor: T) {
for value in &mut self.values {
*value *= factor;
}
}
pub fn scale_rows(&mut self, scaling: &[T]) -> Result<()> {
if scaling.len() != self.nrows {
return Err(LetoError::ShapeMismatch {
lhs: vec![self.nrows],
rhs: vec![scaling.len()],
});
}
for (row, &scale) in scaling.iter().enumerate() {
for index in self.row_ptr[row]..self.row_ptr[row + 1] {
self.values[index] *= scale;
}
}
Ok(())
}
pub fn scale_columns(&mut self, scaling: &[T]) -> Result<()> {
if scaling.len() != self.ncols {
return Err(LetoError::ShapeMismatch {
lhs: vec![self.ncols],
rhs: vec![scaling.len()],
});
}
for (value, &column) in self.values.iter_mut().zip(self.col_indices.iter()) {
*value *= scaling[column];
}
Ok(())
}
#[must_use]
pub fn frobenius_norm(&self) -> T {
self.values
.iter()
.copied()
.fold(T::ZERO, |acc, value| acc + value * value)
.sqrt()
}
#[must_use]
pub fn is_strictly_diagonally_dominant(&self) -> bool {
if self.nrows != self.ncols {
return false;
}
for row in 0..self.nrows {
let csr_row = self.row(row);
let mut diagonal = T::ZERO;
let mut off_diagonal_sum = T::ZERO;
for (&column, &value) in csr_row.col_indices.iter().zip(csr_row.values.iter()) {
let magnitude = value.abs();
if column == row {
diagonal = magnitude;
} else {
off_diagonal_sum += magnitude;
}
}
if diagonal <= off_diagonal_sum {
return false;
}
}
true
}
#[must_use = "transpose returns the transposed sparse matrix"]
pub fn transpose(&self) -> Self {
let mut row_counts = vec![0usize; self.ncols];
for &col in &self.col_indices {
row_counts[col] += 1;
}
let mut row_ptr = Vec::with_capacity(self.ncols + 1);
row_ptr.push(0);
for count in row_counts {
row_ptr.push(row_ptr.last().copied().expect("row_ptr has seed") + count);
}
let mut next = row_ptr[..self.ncols].to_vec();
let mut values = vec![T::ZERO; self.values.len()];
let mut col_indices = vec![0usize; self.col_indices.len()];
for source_row in 0..self.nrows {
for source_index in self.row_ptr[source_row]..self.row_ptr[source_row + 1] {
let transposed_row = self.col_indices[source_index];
let target_index = next[transposed_row];
values[target_index] = self.values[source_index];
col_indices[target_index] = source_row;
next[transposed_row] += 1;
}
}
Self {
values,
col_indices,
row_ptr,
nrows: self.ncols,
ncols: self.nrows,
}
}
#[must_use]
pub fn to_dense(&self) -> Array2<T> {
let mut dense = vec![T::ZERO; self.nrows * self.ncols];
for i in 0..self.nrows {
for p in self.row_ptr[i]..self.row_ptr[i + 1] {
dense[i * self.ncols + self.col_indices[p]] = self.values[p];
}
}
Array2::from_shape_vec([self.nrows, self.ncols], dense).expect("CSR dense shape is valid")
}
}
impl<T: RealScalar> CsrMatrix<T> {
#[must_use = "condition_estimate reports the computed estimate or a shape error"]
pub fn condition_estimate(&self) -> Result<T> {
if self.nrows != self.ncols {
return Err(LetoError::ShapeMismatch {
lhs: vec![self.nrows, self.nrows],
rhs: vec![self.nrows, self.ncols],
});
}
let mut max_ratio = T::ONE;
let near_zero = <T as FloatElement>::from_f64(1.0e-12);
for row in 0..self.nrows {
let csr_row = self.row(row);
let mut diagonal = T::ZERO;
let mut off_diagonal_sum = T::ZERO;
for (&column, &value) in csr_row.col_indices.iter().zip(csr_row.values.iter()) {
let magnitude = value.abs();
if column == row {
diagonal = magnitude;
} else {
off_diagonal_sum += magnitude;
}
}
if diagonal < near_zero {
return Ok(T::INFINITY);
}
let ratio = (off_diagonal_sum + diagonal) / diagonal;
if ratio > max_ratio {
max_ratio = ratio;
}
}
Ok(max_ratio)
}
}