use xingo_sparse::{CscMatrix, CsrMatrix, DenseBlock, Real};
use crate::view::{MatMut, MatRef};
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct OperatorError {
pub message: String,
}
impl OperatorError {
fn new(message: &str) -> Self {
Self {
message: message.to_owned(),
}
}
}
fn check(x: usize, xe: usize, y: usize, ye: usize) -> Result<(), OperatorError> {
if x == xe && y == ye {
Ok(())
} else {
Err(OperatorError::new(
"operator applied to vectors of the wrong length",
))
}
}
pub trait LinearOperator<T: Real = f64> {
fn nrows(&self) -> usize;
fn ncols(&self) -> usize;
fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError>;
fn apply_block(&mut self, x: MatRef<'_, T>, mut y: MatMut<'_, T>) -> Result<(), OperatorError> {
check_block(
x.rows(),
self.ncols(),
y.rows(),
self.nrows(),
x.cols(),
y.cols(),
)?;
for c in 0..x.cols() {
let (Some(xc), Some(yc)) = (x.col(c), y.col_mut(c)) else {
return Err(OperatorError::new("block column out of range"));
};
self.apply(xc, yc)?;
}
Ok(())
}
}
pub trait AdjointOperator<T: Real = f64>: LinearOperator<T> {
fn apply_t(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError>;
fn apply_t_block(
&mut self,
x: MatRef<'_, T>,
mut y: MatMut<'_, T>,
) -> Result<(), OperatorError> {
check_block(
x.rows(),
self.nrows(),
y.rows(),
self.ncols(),
x.cols(),
y.cols(),
)?;
for c in 0..x.cols() {
let (Some(xc), Some(yc)) = (x.col(c), y.col_mut(c)) else {
return Err(OperatorError::new("block column out of range"));
};
self.apply_t(xc, yc)?;
}
Ok(())
}
}
fn check_block(
xr: usize,
xe: usize,
yr: usize,
ye: usize,
xc: usize,
yc: usize,
) -> Result<(), OperatorError> {
if xr == xe && yr == ye && xc == yc {
Ok(())
} else {
Err(OperatorError::new(
"operator applied to blocks of the wrong shape",
))
}
}
impl<T: Real, O: LinearOperator<T> + ?Sized> LinearOperator<T> for &mut O {
fn nrows(&self) -> usize {
(**self).nrows()
}
fn ncols(&self) -> usize {
(**self).ncols()
}
fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
(**self).apply(x, y)
}
fn apply_block(&mut self, x: MatRef<'_, T>, y: MatMut<'_, T>) -> Result<(), OperatorError> {
(**self).apply_block(x, y)
}
}
impl<T: Real, O: AdjointOperator<T> + ?Sized> AdjointOperator<T> for &mut O {
fn apply_t(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
(**self).apply_t(x, y)
}
fn apply_t_block(&mut self, x: MatRef<'_, T>, y: MatMut<'_, T>) -> Result<(), OperatorError> {
(**self).apply_t_block(x, y)
}
}
fn dense_apply<T: Real>(data: &[T], rows: usize, cols: usize, ld: usize, x: &[T], y: &mut [T]) {
y.fill(T::ZERO);
for k in 0..cols {
let xk = x[k];
let a = &data[k * ld..k * ld + rows];
for (yi, &aik) in y.iter_mut().zip(a) {
*yi += aik * xk;
}
}
}
fn dense_apply_t<T: Real>(data: &[T], rows: usize, cols: usize, ld: usize, x: &[T], y: &mut [T]) {
for (j, yj) in y.iter_mut().enumerate().take(cols) {
let a = &data[j * ld..j * ld + rows];
*yj = a.iter().zip(x).map(|(&p, &q)| p * q).sum();
}
}
fn dense_block<T: Real>(
data: &[T],
(rows, cols, ld): (usize, usize, usize),
transpose: bool,
x: MatRef<'_, T>,
mut y: MatMut<'_, T>,
) -> Result<(), OperatorError> {
let (xe, ye) = if transpose {
(rows, cols)
} else {
(cols, rows)
};
check_block(x.rows(), xe, y.rows(), ye, x.cols(), y.cols())?;
for c in 0..x.cols() {
let (Some(xc), Some(yc)) = (x.col(c), y.col_mut(c)) else {
return Err(OperatorError::new("block column out of range"));
};
if transpose {
dense_apply_t(data, rows, cols, ld, xc, yc);
} else {
dense_apply(data, rows, cols, ld, xc, yc);
}
}
Ok(())
}
fn block_parts<T: Real>(b: &DenseBlock<T>) -> Result<(usize, usize, usize), OperatorError> {
if b.data.len() == b.rows.saturating_mul(b.cols) {
Ok((b.rows, b.cols, b.rows))
} else {
Err(OperatorError::new(
"DenseBlock: data.len() differs from rows * cols",
))
}
}
impl<T: Real> LinearOperator<T> for DenseBlock<T> {
fn nrows(&self) -> usize {
self.rows
}
fn ncols(&self) -> usize {
self.cols
}
fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
let (r, c, ld) = block_parts(self)?;
check(x.len(), c, y.len(), r)?;
dense_apply(&self.data, r, c, ld, x, y);
Ok(())
}
fn apply_block(&mut self, x: MatRef<'_, T>, y: MatMut<'_, T>) -> Result<(), OperatorError> {
let parts = block_parts(self)?;
dense_block(&self.data, parts, false, x, y)
}
}
impl<T: Real> AdjointOperator<T> for DenseBlock<T> {
fn apply_t(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
let (r, c, ld) = block_parts(self)?;
check(x.len(), r, y.len(), c)?;
dense_apply_t(&self.data, r, c, ld, x, y);
Ok(())
}
fn apply_t_block(&mut self, x: MatRef<'_, T>, y: MatMut<'_, T>) -> Result<(), OperatorError> {
let parts = block_parts(self)?;
dense_block(&self.data, parts, true, x, y)
}
}
impl<T: Real> LinearOperator<T> for MatRef<'_, T> {
fn nrows(&self) -> usize {
self.rows()
}
fn ncols(&self) -> usize {
self.cols()
}
fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
check(x.len(), self.cols(), y.len(), self.rows())?;
dense_apply(self.raw(), self.rows(), self.cols(), self.ld(), x, y);
Ok(())
}
fn apply_block(&mut self, x: MatRef<'_, T>, y: MatMut<'_, T>) -> Result<(), OperatorError> {
let parts = (self.rows(), self.cols(), self.ld());
dense_block(self.raw(), parts, false, x, y)
}
}
impl<T: Real> AdjointOperator<T> for MatRef<'_, T> {
fn apply_t(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
check(x.len(), self.rows(), y.len(), self.cols())?;
dense_apply_t(self.raw(), self.rows(), self.cols(), self.ld(), x, y);
Ok(())
}
fn apply_t_block(&mut self, x: MatRef<'_, T>, y: MatMut<'_, T>) -> Result<(), OperatorError> {
let parts = (self.rows(), self.cols(), self.ld());
dense_block(self.raw(), parts, true, x, y)
}
}
const BAD_SPARSE: &str = "sparse matrix with inconsistent fields (index out of range)";
fn segment<'a, T>(
ptr: &[usize],
idx: &'a [u32],
val: &'a [T],
j: usize,
) -> Result<(&'a [u32], &'a [T]), OperatorError> {
let (Some(&a), Some(&b)) = (ptr.get(j), ptr.get(j + 1)) else {
return Err(OperatorError::new(BAD_SPARSE));
};
match (idx.get(a..b), val.get(a..b)) {
(Some(i), Some(v)) => Ok((i, v)),
_ => Err(OperatorError::new(BAD_SPARSE)),
}
}
fn scatter<T: Real>(rows: &[u32], vals: &[T], t: T, y: &mut [T]) -> Result<(), OperatorError> {
for (&i, &v) in rows.iter().zip(vals) {
let Some(yi) = y.get_mut(i as usize) else {
return Err(OperatorError::new(BAD_SPARSE));
};
*yi += v * t;
}
Ok(())
}
fn gather<T: Real>(rows: &[u32], vals: &[T], x: &[T]) -> Result<T, OperatorError> {
let mut s = T::ZERO;
for (&i, &v) in rows.iter().zip(vals) {
let Some(&xi) = x.get(i as usize) else {
return Err(OperatorError::new(BAD_SPARSE));
};
s += v * xi;
}
Ok(s)
}
impl<T: Real> LinearOperator<T> for CscMatrix<T> {
fn nrows(&self) -> usize {
self.n_rows()
}
fn ncols(&self) -> usize {
self.n_cols()
}
fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
check(x.len(), self.n_cols(), y.len(), self.n_rows())?;
y.fill(T::ZERO);
for (j, &xj) in x.iter().enumerate() {
if crate::real::is_exact_zero(xj) {
continue;
}
let (r, v) = segment(&self.col_ptr, &self.row_idx, &self.val, j)?;
scatter(r, v, xj, y)?;
}
Ok(())
}
}
impl<T: Real> AdjointOperator<T> for CscMatrix<T> {
fn apply_t(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
check(x.len(), self.n_rows(), y.len(), self.n_cols())?;
for (j, yj) in y.iter_mut().enumerate() {
let (r, v) = segment(&self.col_ptr, &self.row_idx, &self.val, j)?;
*yj = gather(r, v, x)?;
}
Ok(())
}
}
impl<T: Real> LinearOperator<T> for CsrMatrix<T> {
fn nrows(&self) -> usize {
self.n_rows()
}
fn ncols(&self) -> usize {
self.n_cols()
}
fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
check(x.len(), self.n_cols(), y.len(), self.n_rows())?;
for (i, yi) in y.iter_mut().enumerate() {
let (c, v) = segment(&self.row_ptr, &self.col_idx, &self.val, i)?;
*yi = gather(c, v, x)?;
}
Ok(())
}
}
impl<T: Real> AdjointOperator<T> for CsrMatrix<T> {
fn apply_t(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
check(x.len(), self.n_rows(), y.len(), self.n_cols())?;
y.fill(T::ZERO);
for (i, &xi) in x.iter().enumerate() {
let (c, v) = segment(&self.row_ptr, &self.col_idx, &self.val, i)?;
scatter(c, v, xi, y)?;
}
Ok(())
}
}
#[derive(Debug)]
pub struct FnOperator<F> {
nrows: usize,
ncols: usize,
f: F,
}
#[derive(Debug)]
pub struct FnAdjointOperator<F, G> {
nrows: usize,
ncols: usize,
f: F,
g: G,
}
pub fn from_fn<T, F>(nrows: usize, ncols: usize, f: F) -> FnOperator<F>
where
T: Real,
F: FnMut(&[T], &mut [T]) -> Result<(), OperatorError>,
{
FnOperator { nrows, ncols, f }
}
pub fn from_fns<T, F, G>(nrows: usize, ncols: usize, f: F, g: G) -> FnAdjointOperator<F, G>
where
T: Real,
F: FnMut(&[T], &mut [T]) -> Result<(), OperatorError>,
G: FnMut(&[T], &mut [T]) -> Result<(), OperatorError>,
{
FnAdjointOperator { nrows, ncols, f, g }
}
impl<T: Real, F: FnMut(&[T], &mut [T]) -> Result<(), OperatorError>> LinearOperator<T>
for FnOperator<F>
{
fn nrows(&self) -> usize {
self.nrows
}
fn ncols(&self) -> usize {
self.ncols
}
fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
(self.f)(x, y)
}
}
impl<T, F, G> LinearOperator<T> for FnAdjointOperator<F, G>
where
T: Real,
F: FnMut(&[T], &mut [T]) -> Result<(), OperatorError>,
{
fn nrows(&self) -> usize {
self.nrows
}
fn ncols(&self) -> usize {
self.ncols
}
fn apply(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
(self.f)(x, y)
}
}
impl<T, F, G> AdjointOperator<T> for FnAdjointOperator<F, G>
where
T: Real,
F: FnMut(&[T], &mut [T]) -> Result<(), OperatorError>,
G: FnMut(&[T], &mut [T]) -> Result<(), OperatorError>,
{
fn apply_t(&mut self, x: &[T], y: &mut [T]) -> Result<(), OperatorError> {
(self.g)(x, y)
}
}
#[cfg(test)]
#[allow(clippy::float_cmp)] mod tests {
use super::*;
use xingo_sparse::{Col, Row};
fn dense() -> DenseBlock<f64> {
DenseBlock {
rows: 4,
cols: 3,
data: vec![1.0, 0.0, 4.0, 0.0, 0.0, 3.0, 0.0, 6.0, 2.0, 0.0, 5.0, 0.0],
}
}
fn csc() -> CscMatrix<f64> {
let d = dense();
let mut t = Vec::new();
for j in 0..3 {
for i in 0..4 {
if d.get(i, j) != 0.0 {
t.push((Row::from_usize(i), Col::from_usize(j), d.get(i, j)));
}
}
}
CscMatrix::from_triplets(4, 3, &t).unwrap()
}
fn check_op<O: AdjointOperator<f64>>(op: &mut O) {
let x = [1.0, -2.0, 0.5];
let mut y = [9.0; 4];
op.apply(&x, &mut y).unwrap();
assert_eq!(y, [2.0, -6.0, 6.5, -12.0]);
let z = [1.0, 1.0, -1.0, 2.0];
let mut w = [9.0; 3];
op.apply_t(&z, &mut w).unwrap();
assert_eq!(w, [-3.0, 15.0, -3.0]);
assert!(op.apply(&x[..2], &mut y).is_err());
assert!(op.apply_t(&z, &mut y).is_err());
let xb = [1.0, -2.0, 0.5, 0.3, 0.7, -1.1];
let mut yb = [0.0; 8];
op.apply_block(
MatRef::new(3, 2, 3, &xb).unwrap(),
MatMut::new(4, 2, 4, &mut yb).unwrap(),
)
.unwrap();
let mut y2 = [0.0; 4];
op.apply(&xb[3..], &mut y2).unwrap();
assert_eq!(&yb[4..], &y2);
let mut wb = [0.0; 6];
let zb = [z, [0.5, -0.25, 2.0, 1.5]].concat();
op.apply_t_block(
MatRef::new(4, 2, 4, &zb).unwrap(),
MatMut::new(3, 2, 3, &mut wb).unwrap(),
)
.unwrap();
let mut w2 = [0.0; 3];
op.apply_t(&zb[4..], &mut w2).unwrap();
assert_eq!(&wb[3..], &w2);
assert!(
op.apply_block(
MatRef::new(3, 2, 3, &xb).unwrap(),
MatMut::new(3, 2, 3, &mut wb).unwrap()
)
.is_err()
);
}
fn by_value<O: AdjointOperator<f64>>(mut o: O) {
check_op(&mut o);
}
#[test]
fn every_storage_applies_the_same_matrix() {
check_op(&mut dense());
check_op(&mut csc());
check_op(&mut csc().to_csr());
let d = dense();
let mut padded = vec![f64::NAN; 15];
for j in 0..3 {
for i in 0..4 {
padded[i + 5 * j] = d.get(i, j);
}
}
check_op(&mut MatRef::new(4, 3, 5, &padded).unwrap());
let (a, b) = (d.clone(), d.clone());
let mut f = from_fns(
4,
3,
move |x: &[f64], y: &mut [f64]| a.clone().apply(x, y),
move |x: &[f64], y: &mut [f64]| b.clone().apply_t(x, y),
);
check_op(&mut f);
by_value(&mut f);
let mut g = from_fn(1, 1, |_: &[f64], _: &mut [f64]| {
Err(OperatorError::new("inner solve failed"))
});
assert_eq!(
g.apply(&[1.0], &mut [0.0]).unwrap_err().message,
"inner solve failed"
);
assert_eq!((g.nrows(), g.ncols()), (1, 1));
}
#[test]
fn inconsistent_fields_are_errors_not_panics() {
let mut a = csc();
a.row_idx[0] = 99;
assert!(a.apply(&[1.0, 1.0, 1.0], &mut [0.0; 4]).is_err());
assert!(a.apply_t(&[1.0; 4], &mut [0.0; 3]).is_err());
let mut c = csc().to_csr();
c.row_ptr[1] = 1000;
assert!(c.apply(&[1.0; 3], &mut [0.0; 4]).is_err());
let mut d = dense();
d.data.pop();
assert!(d.apply(&[1.0; 3], &mut [0.0; 4]).is_err());
assert!(d.apply_t(&[1.0; 4], &mut [0.0; 3]).is_err());
}
}