//! Iterative linear system solvers over ndarray matrices.

use std::fmt;

use nabled_core::scalar::NabledReal;
use nabled_linalg::lu;
use ndarray::{Array1, Array2, ArrayBase, ArrayView1, ArrayView2, ArrayViewMut1, Data, Ix1};
use num_complex::Complex64;

const DEFAULT_TOLERANCE: f64 = 1.0e-12;

/// Configuration for iterative solvers.
#[derive(Debug, Clone)]
pub struct IterativeConfig<T = f64> {
    /// Relative residual tolerance.
    pub tolerance:      T,
    /// Maximum iterations.
    pub max_iterations: usize,
}

impl IterativeConfig<f64> {
    /// Default configuration for `f64`.
    #[must_use]
    pub const fn default_f64() -> Self { Self { tolerance: 1e-10, max_iterations: 1000 } }
}

impl Default for IterativeConfig<f64> {
    fn default() -> Self { Self::default_f64() }
}

impl IterativeConfig<f32> {
    /// Default configuration for `f32`.
    #[must_use]
    pub const fn default_f32() -> Self { Self { tolerance: 1e-6, max_iterations: 1000 } }
}

impl Default for IterativeConfig<f32> {
    fn default() -> Self { Self::default_f32() }
}

/// Error type for iterative solvers.
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum IterativeError {
    /// Matrix is empty.
    EmptyMatrix,
    /// Dimensions do not align.
    DimensionMismatch,
    /// Maximum iterations reached without convergence.
    MaxIterationsExceeded,
    /// Matrix is not positive definite (CG).
    NotPositiveDefinite,
    /// Algorithm breakdown.
    Breakdown,
}

impl fmt::Display for IterativeError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            IterativeError::EmptyMatrix => write!(f, "Matrix is empty"),
            IterativeError::DimensionMismatch => write!(f, "Dimension mismatch"),
            IterativeError::MaxIterationsExceeded => write!(f, "Maximum iterations exceeded"),
            IterativeError::NotPositiveDefinite => write!(f, "Matrix is not positive definite"),
            IterativeError::Breakdown => write!(f, "Algorithm breakdown"),
        }
    }
}

impl std::error::Error for IterativeError {}

fn default_tolerance<T: NabledReal>() -> T {
    T::from_f64(DEFAULT_TOLERANCE).unwrap_or_else(T::epsilon)
}

fn vector_norm<T, S>(vector: &ArrayBase<S, Ix1>) -> T
where
    T: NabledReal,
    S: Data<Elem = T>,
{
    vector
        .iter()
        .map(|value| *value * *value)
        .fold(T::zero(), |acc, value| acc + value)
        .sqrt()
}

fn vector_norm_complex<S>(vector: &ArrayBase<S, Ix1>) -> f64
where
    S: Data<Elem = Complex64>,
{
    vector.iter().map(Complex64::norm_sqr).sum::<f64>().sqrt()
}

#[cfg(all(feature = "lapack-provider", feature = "magma-system"))]
trait IterativeLinearScalar:
    NabledReal + std::ops::SubAssign + ndarray_linalg::Lapack + lu::LuProviderScalar
{
}

#[cfg(all(feature = "lapack-provider", feature = "magma-system"))]
impl<T> IterativeLinearScalar for T where
    T: NabledReal + std::ops::SubAssign + ndarray_linalg::Lapack + lu::LuProviderScalar
{
}

#[cfg(all(feature = "lapack-provider", not(feature = "magma-system")))]
trait IterativeLinearScalar: NabledReal + std::ops::SubAssign + ndarray_linalg::Lapack {}

#[cfg(all(feature = "lapack-provider", not(feature = "magma-system")))]
impl<T> IterativeLinearScalar for T where
    T: NabledReal + std::ops::SubAssign + ndarray_linalg::Lapack
{
}

#[cfg(all(not(feature = "lapack-provider"), feature = "magma-system"))]
trait IterativeLinearScalar: NabledReal + std::ops::SubAssign + lu::LuProviderScalar {}

#[cfg(all(not(feature = "lapack-provider"), feature = "magma-system"))]
impl<T> IterativeLinearScalar for T where T: NabledReal + std::ops::SubAssign + lu::LuProviderScalar {}

#[cfg(not(any(feature = "lapack-provider", feature = "magma-system")))]
trait IterativeLinearScalar: NabledReal + std::ops::SubAssign {}

#[cfg(not(any(feature = "lapack-provider", feature = "magma-system")))]
impl<T> IterativeLinearScalar for T where T: NabledReal + std::ops::SubAssign {}

/// Conjugate Gradient for SPD systems `Ax=b`.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
pub fn conjugate_gradient<T>(
    matrix_a: &Array2<T>,
    matrix_b: &Array1<T>,
    config: &IterativeConfig<T>,
) -> Result<Array1<T>, IterativeError>
where
    T: NabledReal,
{
    let mut output = Array1::<T>::zeros(matrix_b.len());
    conjugate_gradient_view_into(&matrix_a.view(), &matrix_b.view(), config, output.view_mut())?;
    Ok(output)
}

/// Conjugate Gradient for SPD systems `Ax=b` from matrix/vector views.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
pub fn conjugate_gradient_view<T>(
    matrix_a: &ArrayView2<'_, T>,
    matrix_b: &ArrayView1<'_, T>,
    config: &IterativeConfig<T>,
) -> Result<Array1<T>, IterativeError>
where
    T: NabledReal,
{
    let mut output = Array1::<T>::zeros(matrix_b.len());
    conjugate_gradient_view_into(matrix_a, matrix_b, config, output.view_mut())?;
    Ok(output)
}

/// Conjugate Gradient for SPD systems `Ax=b` into a caller-provided output vector.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
pub fn conjugate_gradient_into<T>(
    matrix_a: &Array2<T>,
    matrix_b: &Array1<T>,
    config: &IterativeConfig<T>,
    output: &mut Array1<T>,
) -> Result<(), IterativeError>
where
    T: NabledReal,
{
    conjugate_gradient_view_into(&matrix_a.view(), &matrix_b.view(), config, output.view_mut())
}

/// Conjugate Gradient for SPD systems `Ax=b` from matrix/vector views into a caller-provided
/// output vector.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
pub fn conjugate_gradient_view_into<T>(
    matrix_a: &ArrayView2<'_, T>,
    matrix_b: &ArrayView1<'_, T>,
    config: &IterativeConfig<T>,
    mut output: ArrayViewMut1<'_, T>,
) -> Result<(), IterativeError>
where
    T: NabledReal,
{
    if matrix_a.is_empty() || matrix_b.is_empty() {
        return Err(IterativeError::EmptyMatrix);
    }
    if matrix_a.nrows() != matrix_a.ncols() || matrix_a.nrows() != matrix_b.len() {
        return Err(IterativeError::DimensionMismatch);
    }
    if output.len() != matrix_b.len() {
        return Err(IterativeError::DimensionMismatch);
    }

    let n = matrix_b.len();
    output.fill(T::zero());
    let mut r = matrix_b.to_owned();
    let mut p = r.clone();
    let mut rs_old = r.dot(&r);

    let tolerance = config.tolerance.max(default_tolerance::<T>());
    if rs_old.sqrt() <= tolerance {
        return Ok(());
    }

    for _ in 0..config.max_iterations {
        let ap = matrix_a.dot(&p);
        let curvature = p.dot(&ap);
        if curvature <= tolerance {
            return Err(IterativeError::NotPositiveDefinite);
        }

        let alpha = rs_old / curvature;
        for idx in 0..n {
            output[idx] += alpha * p[idx];
            r[idx] -= alpha * ap[idx];
        }

        let rs_new = r.dot(&r);
        if rs_new.sqrt() <= tolerance {
            return Ok(());
        }

        let beta = rs_new / rs_old;
        for idx in 0..n {
            p[idx] = r[idx] + beta * p[idx];
        }
        rs_old = rs_new;
    }

    Err(IterativeError::MaxIterationsExceeded)
}

/// Conjugate Gradient for Hermitian positive-definite systems `Ax=b`.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
pub fn conjugate_gradient_complex(
    matrix_a: &Array2<Complex64>,
    matrix_b: &Array1<Complex64>,
    config: &IterativeConfig<f64>,
) -> Result<Array1<Complex64>, IterativeError> {
    let mut output = Array1::<Complex64>::zeros(matrix_b.len());
    conjugate_gradient_complex_view_into(
        &matrix_a.view(),
        &matrix_b.view(),
        config,
        output.view_mut(),
    )?;
    Ok(output)
}

/// Conjugate Gradient for Hermitian positive-definite systems `Ax=b` from views.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
pub fn conjugate_gradient_complex_view(
    matrix_a: &ArrayView2<'_, Complex64>,
    matrix_b: &ArrayView1<'_, Complex64>,
    config: &IterativeConfig<f64>,
) -> Result<Array1<Complex64>, IterativeError> {
    let mut output = Array1::<Complex64>::zeros(matrix_b.len());
    conjugate_gradient_complex_view_into(matrix_a, matrix_b, config, output.view_mut())?;
    Ok(output)
}

/// Conjugate Gradient for Hermitian positive-definite systems `Ax=b` into a caller-provided
/// output vector.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
pub fn conjugate_gradient_complex_into(
    matrix_a: &Array2<Complex64>,
    matrix_b: &Array1<Complex64>,
    config: &IterativeConfig<f64>,
    output: &mut Array1<Complex64>,
) -> Result<(), IterativeError> {
    conjugate_gradient_complex_view_into(
        &matrix_a.view(),
        &matrix_b.view(),
        config,
        output.view_mut(),
    )
}

/// Conjugate Gradient for Hermitian positive-definite systems `Ax=b` from views into a
/// caller-provided output vector.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
pub fn conjugate_gradient_complex_view_into(
    matrix_a: &ArrayView2<'_, Complex64>,
    matrix_b: &ArrayView1<'_, Complex64>,
    config: &IterativeConfig<f64>,
    mut output: ArrayViewMut1<'_, Complex64>,
) -> Result<(), IterativeError> {
    if matrix_a.is_empty() || matrix_b.is_empty() {
        return Err(IterativeError::EmptyMatrix);
    }
    if matrix_a.nrows() != matrix_a.ncols() || matrix_a.nrows() != matrix_b.len() {
        return Err(IterativeError::DimensionMismatch);
    }
    if output.len() != matrix_b.len() {
        return Err(IterativeError::DimensionMismatch);
    }

    let n = matrix_b.len();
    output.fill(Complex64::default());
    let mut r = matrix_b.to_owned();
    let mut p = r.clone();
    let mut rs_old = r.iter().zip(r.iter()).map(|(lhs, rhs)| lhs.conj() * rhs).sum::<Complex64>();
    let tolerance = config.tolerance.max(DEFAULT_TOLERANCE);

    if rs_old.re.max(0.0).sqrt() <= tolerance {
        return Ok(());
    }

    for _ in 0..config.max_iterations {
        let ap = matrix_a.dot(&p);
        let curvature =
            p.iter().zip(ap.iter()).map(|(lhs, rhs)| lhs.conj() * rhs).sum::<Complex64>();
        if curvature.re <= tolerance || curvature.norm() <= tolerance {
            return Err(IterativeError::NotPositiveDefinite);
        }

        let alpha = rs_old / curvature;
        for idx in 0..n {
            output[idx] += alpha * p[idx];
            r[idx] -= alpha * ap[idx];
        }

        let rs_new = r.iter().zip(r.iter()).map(|(lhs, rhs)| lhs.conj() * rhs).sum::<Complex64>();
        if rs_new.re.max(0.0).sqrt() <= tolerance {
            return Ok(());
        }

        if rs_old.norm() <= tolerance {
            return Err(IterativeError::Breakdown);
        }
        let beta = rs_new / rs_old;
        for idx in 0..n {
            p[idx] = r[idx] + beta * p[idx];
        }
        rs_old = rs_new;
    }

    Err(IterativeError::MaxIterationsExceeded)
}

fn solve_linear<T>(
    matrix: &ArrayView2<'_, T>,
    rhs: &ArrayView1<'_, T>,
) -> Result<Array1<T>, IterativeError>
where
    T: IterativeLinearScalar,
{
    lu::solve_view(matrix, rhs).map_err(|_| IterativeError::Breakdown)
}

/// GMRES for general systems `Ax=b`.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(all(feature = "lapack-provider", feature = "magma-system"))]
pub fn gmres<T>(
    matrix_a: &Array2<T>,
    matrix_b: &Array1<T>,
    config: &IterativeConfig<T>,
) -> Result<Array1<T>, IterativeError>
where
    T: NabledReal + std::ops::SubAssign + ndarray_linalg::Lapack + lu::LuProviderScalar,
{
    let mut output = Array1::<T>::zeros(matrix_b.len());
    gmres_view_into(&matrix_a.view(), &matrix_b.view(), config, output.view_mut())?;
    Ok(output)
}

/// GMRES for general systems `Ax=b`.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(all(feature = "lapack-provider", not(feature = "magma-system")))]
pub fn gmres<T>(
    matrix_a: &Array2<T>,
    matrix_b: &Array1<T>,
    config: &IterativeConfig<T>,
) -> Result<Array1<T>, IterativeError>
where
    T: NabledReal + std::ops::SubAssign + ndarray_linalg::Lapack,
{
    let mut output = Array1::<T>::zeros(matrix_b.len());
    gmres_view_into(&matrix_a.view(), &matrix_b.view(), config, output.view_mut())?;
    Ok(output)
}

/// GMRES for general systems `Ax=b`.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(all(not(feature = "lapack-provider"), feature = "magma-system"))]
pub fn gmres<T>(
    matrix_a: &Array2<T>,
    matrix_b: &Array1<T>,
    config: &IterativeConfig<T>,
) -> Result<Array1<T>, IterativeError>
where
    T: NabledReal + std::ops::SubAssign + lu::LuProviderScalar,
{
    let mut output = Array1::<T>::zeros(matrix_b.len());
    gmres_view_into(&matrix_a.view(), &matrix_b.view(), config, output.view_mut())?;
    Ok(output)
}

/// GMRES for general systems `Ax=b`.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(not(any(feature = "lapack-provider", feature = "magma-system")))]
pub fn gmres<T>(
    matrix_a: &Array2<T>,
    matrix_b: &Array1<T>,
    config: &IterativeConfig<T>,
) -> Result<Array1<T>, IterativeError>
where
    T: NabledReal + std::ops::SubAssign,
{
    let mut output = Array1::<T>::zeros(matrix_b.len());
    gmres_view_into(&matrix_a.view(), &matrix_b.view(), config, output.view_mut())?;
    Ok(output)
}

fn gmres_impl<T>(
    matrix_a: &ArrayView2<'_, T>,
    matrix_b: &ArrayView1<'_, T>,
    config: &IterativeConfig<T>,
    mut output: ArrayViewMut1<'_, T>,
) -> Result<(), IterativeError>
where
    T: IterativeLinearScalar,
{
    if matrix_a.is_empty() || matrix_b.is_empty() {
        return Err(IterativeError::EmptyMatrix);
    }
    if matrix_a.nrows() != matrix_a.ncols() || matrix_a.nrows() != matrix_b.len() {
        return Err(IterativeError::DimensionMismatch);
    }
    if output.len() != matrix_b.len() {
        return Err(IterativeError::DimensionMismatch);
    }

    let n = matrix_b.len();
    let m = n.min(config.max_iterations.max(1));
    let mut basis = Array2::<T>::zeros((n, m + 1));
    let mut hessenberg = Array2::<T>::zeros((m + 1, m));

    let beta = vector_norm(matrix_b);
    let tolerance = config.tolerance.max(default_tolerance::<T>());
    if beta <= tolerance {
        output.fill(T::zero());
        return Ok(());
    }

    for row in 0..n {
        basis[[row, 0]] = matrix_b[row] / beta;
    }

    let mut effective_m = m;
    for j in 0..m {
        let mut w = matrix_a.dot(&basis.column(j));

        for i in 0..=j {
            let vi = basis.column(i);
            let hij = vi.dot(&w);
            hessenberg[[i, j]] = hij;
            for row in 0..n {
                w[row] -= hij * basis[[row, i]];
            }
        }

        let norm_w = vector_norm(&w);
        hessenberg[[j + 1, j]] = norm_w;
        if norm_w <= tolerance {
            effective_m = j + 1;
            break;
        }
        for row in 0..n {
            basis[[row, j + 1]] = w[row] / norm_w;
        }
    }

    let h = hessenberg.slice(ndarray::s![..(effective_m + 1), ..effective_m]);
    let ht = h.t();
    let normal_matrix = ht.dot(&h);

    let mut rhs_ls = Array1::<T>::zeros(effective_m + 1);
    rhs_ls[0] = beta;
    let normal_rhs = ht.dot(&rhs_ls);

    let y = solve_linear(&normal_matrix.view(), &normal_rhs.view())?;
    output.fill(T::zero());
    for column in 0..effective_m {
        let coefficient = y[column];
        for row in 0..n {
            output[row] += basis[[row, column]] * coefficient;
        }
    }

    let residual = matrix_b - &matrix_a.dot(&output.view());
    if vector_norm(&residual) <= tolerance {
        Ok(())
    } else {
        Err(IterativeError::MaxIterationsExceeded)
    }
}

/// GMRES for general systems `Ax=b` from matrix/vector views.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(all(feature = "lapack-provider", feature = "magma-system"))]
pub fn gmres_view<T>(
    matrix_a: &ArrayView2<'_, T>,
    matrix_b: &ArrayView1<'_, T>,
    config: &IterativeConfig<T>,
) -> Result<Array1<T>, IterativeError>
where
    T: NabledReal + std::ops::SubAssign + ndarray_linalg::Lapack + lu::LuProviderScalar,
{
    let mut output = Array1::<T>::zeros(matrix_b.len());
    gmres_impl(matrix_a, matrix_b, config, output.view_mut())?;
    Ok(output)
}

/// GMRES for general systems `Ax=b` from matrix/vector views.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(all(feature = "lapack-provider", not(feature = "magma-system")))]
pub fn gmres_view<T>(
    matrix_a: &ArrayView2<'_, T>,
    matrix_b: &ArrayView1<'_, T>,
    config: &IterativeConfig<T>,
) -> Result<Array1<T>, IterativeError>
where
    T: NabledReal + std::ops::SubAssign + ndarray_linalg::Lapack,
{
    let mut output = Array1::<T>::zeros(matrix_b.len());
    gmres_impl(matrix_a, matrix_b, config, output.view_mut())?;
    Ok(output)
}

/// GMRES for general systems `Ax=b` from matrix/vector views.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(all(not(feature = "lapack-provider"), feature = "magma-system"))]
pub fn gmres_view<T>(
    matrix_a: &ArrayView2<'_, T>,
    matrix_b: &ArrayView1<'_, T>,
    config: &IterativeConfig<T>,
) -> Result<Array1<T>, IterativeError>
where
    T: NabledReal + std::ops::SubAssign + lu::LuProviderScalar,
{
    let mut output = Array1::<T>::zeros(matrix_b.len());
    gmres_impl(matrix_a, matrix_b, config, output.view_mut())?;
    Ok(output)
}

/// GMRES for general systems `Ax=b` from matrix/vector views.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(not(any(feature = "lapack-provider", feature = "magma-system")))]
pub fn gmres_view<T>(
    matrix_a: &ArrayView2<'_, T>,
    matrix_b: &ArrayView1<'_, T>,
    config: &IterativeConfig<T>,
) -> Result<Array1<T>, IterativeError>
where
    T: NabledReal + std::ops::SubAssign,
{
    let mut output = Array1::<T>::zeros(matrix_b.len());
    gmres_impl(matrix_a, matrix_b, config, output.view_mut())?;
    Ok(output)
}

/// GMRES for general systems `Ax=b` from matrix/vector views into a caller-provided output
/// vector.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(all(feature = "lapack-provider", feature = "magma-system"))]
pub fn gmres_view_into<T>(
    matrix_a: &ArrayView2<'_, T>,
    matrix_b: &ArrayView1<'_, T>,
    config: &IterativeConfig<T>,
    output: ArrayViewMut1<'_, T>,
) -> Result<(), IterativeError>
where
    T: NabledReal + std::ops::SubAssign + ndarray_linalg::Lapack + lu::LuProviderScalar,
{
    gmres_impl(matrix_a, matrix_b, config, output)
}

/// GMRES for general systems `Ax=b` from matrix/vector views into a caller-provided output
/// vector.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(all(feature = "lapack-provider", not(feature = "magma-system")))]
pub fn gmres_view_into<T>(
    matrix_a: &ArrayView2<'_, T>,
    matrix_b: &ArrayView1<'_, T>,
    config: &IterativeConfig<T>,
    output: ArrayViewMut1<'_, T>,
) -> Result<(), IterativeError>
where
    T: NabledReal + std::ops::SubAssign + ndarray_linalg::Lapack,
{
    gmres_impl(matrix_a, matrix_b, config, output)
}

/// GMRES for general systems `Ax=b` from matrix/vector views into a caller-provided output
/// vector.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(all(not(feature = "lapack-provider"), feature = "magma-system"))]
pub fn gmres_view_into<T>(
    matrix_a: &ArrayView2<'_, T>,
    matrix_b: &ArrayView1<'_, T>,
    config: &IterativeConfig<T>,
    output: ArrayViewMut1<'_, T>,
) -> Result<(), IterativeError>
where
    T: NabledReal + std::ops::SubAssign + lu::LuProviderScalar,
{
    gmres_impl(matrix_a, matrix_b, config, output)
}

/// GMRES for general systems `Ax=b` from matrix/vector views into a caller-provided output
/// vector.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(not(any(feature = "lapack-provider", feature = "magma-system")))]
pub fn gmres_view_into<T>(
    matrix_a: &ArrayView2<'_, T>,
    matrix_b: &ArrayView1<'_, T>,
    config: &IterativeConfig<T>,
    output: ArrayViewMut1<'_, T>,
) -> Result<(), IterativeError>
where
    T: NabledReal + std::ops::SubAssign,
{
    gmres_impl(matrix_a, matrix_b, config, output)
}

/// GMRES for general systems `Ax=b` into a caller-provided output vector.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(all(feature = "lapack-provider", feature = "magma-system"))]
pub fn gmres_into<T>(
    matrix_a: &Array2<T>,
    matrix_b: &Array1<T>,
    config: &IterativeConfig<T>,
    output: &mut Array1<T>,
) -> Result<(), IterativeError>
where
    T: NabledReal + std::ops::SubAssign + ndarray_linalg::Lapack + lu::LuProviderScalar,
{
    gmres_view_into(&matrix_a.view(), &matrix_b.view(), config, output.view_mut())
}

/// GMRES for general systems `Ax=b` into a caller-provided output vector.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(all(feature = "lapack-provider", not(feature = "magma-system")))]
pub fn gmres_into<T>(
    matrix_a: &Array2<T>,
    matrix_b: &Array1<T>,
    config: &IterativeConfig<T>,
    output: &mut Array1<T>,
) -> Result<(), IterativeError>
where
    T: NabledReal + std::ops::SubAssign + ndarray_linalg::Lapack,
{
    gmres_view_into(&matrix_a.view(), &matrix_b.view(), config, output.view_mut())
}

/// GMRES for general systems `Ax=b` into a caller-provided output vector.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(all(not(feature = "lapack-provider"), feature = "magma-system"))]
pub fn gmres_into<T>(
    matrix_a: &Array2<T>,
    matrix_b: &Array1<T>,
    config: &IterativeConfig<T>,
    output: &mut Array1<T>,
) -> Result<(), IterativeError>
where
    T: NabledReal + std::ops::SubAssign + lu::LuProviderScalar,
{
    gmres_view_into(&matrix_a.view(), &matrix_b.view(), config, output.view_mut())
}

/// GMRES for general systems `Ax=b` into a caller-provided output vector.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
#[cfg(not(any(feature = "lapack-provider", feature = "magma-system")))]
pub fn gmres_into<T>(
    matrix_a: &Array2<T>,
    matrix_b: &Array1<T>,
    config: &IterativeConfig<T>,
    output: &mut Array1<T>,
) -> Result<(), IterativeError>
where
    T: NabledReal + std::ops::SubAssign,
{
    gmres_view_into(&matrix_a.view(), &matrix_b.view(), config, output.view_mut())
}

/// GMRES for complex general systems `Ax=b`.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
pub fn gmres_complex(
    matrix_a: &Array2<Complex64>,
    matrix_b: &Array1<Complex64>,
    config: &IterativeConfig<f64>,
) -> Result<Array1<Complex64>, IterativeError> {
    let mut output = Array1::<Complex64>::zeros(matrix_b.len());
    gmres_complex_view_into(&matrix_a.view(), &matrix_b.view(), config, output.view_mut())?;
    Ok(output)
}

/// GMRES for general complex systems `Ax=b` from views.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
pub fn gmres_complex_view(
    matrix_a: &ArrayView2<'_, Complex64>,
    matrix_b: &ArrayView1<'_, Complex64>,
    config: &IterativeConfig<f64>,
) -> Result<Array1<Complex64>, IterativeError> {
    let mut output = Array1::<Complex64>::zeros(matrix_b.len());
    gmres_complex_view_into(matrix_a, matrix_b, config, output.view_mut())?;
    Ok(output)
}

/// GMRES for general complex systems `Ax=b` into a caller-provided output vector.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
pub fn gmres_complex_into(
    matrix_a: &Array2<Complex64>,
    matrix_b: &Array1<Complex64>,
    config: &IterativeConfig<f64>,
    output: &mut Array1<Complex64>,
) -> Result<(), IterativeError> {
    gmres_complex_view_into(&matrix_a.view(), &matrix_b.view(), config, output.view_mut())
}

/// GMRES for general complex systems `Ax=b` from views into a caller-provided output vector.
///
/// # Errors
/// Returns an error when inputs are invalid or convergence fails.
pub fn gmres_complex_view_into(
    matrix_a: &ArrayView2<'_, Complex64>,
    matrix_b: &ArrayView1<'_, Complex64>,
    config: &IterativeConfig<f64>,
    mut output: ArrayViewMut1<'_, Complex64>,
) -> Result<(), IterativeError> {
    if matrix_a.is_empty() || matrix_b.is_empty() {
        return Err(IterativeError::EmptyMatrix);
    }
    if matrix_a.nrows() != matrix_a.ncols() || matrix_a.nrows() != matrix_b.len() {
        return Err(IterativeError::DimensionMismatch);
    }
    if output.len() != matrix_b.len() {
        return Err(IterativeError::DimensionMismatch);
    }

    let dimension = matrix_b.len();
    let krylov_dim = dimension.min(config.max_iterations.max(1));
    let mut basis = Array2::<Complex64>::zeros((dimension, krylov_dim + 1));
    let mut hessenberg = Array2::<Complex64>::zeros((krylov_dim + 1, krylov_dim));
    let tolerance = config.tolerance.max(DEFAULT_TOLERANCE);

    let beta = vector_norm_complex(matrix_b);
    if beta <= tolerance {
        output.fill(Complex64::default());
        return Ok(());
    }

    for row in 0..dimension {
        basis[[row, 0]] = matrix_b[row] / beta;
    }

    let mut effective_krylov_dim = krylov_dim;
    for column in 0..krylov_dim {
        let mut arnoldi_vector = matrix_a.dot(&basis.column(column));

        for basis_col in 0..=column {
            let basis_vector = basis.column(basis_col);
            let hessenberg_entry = basis_vector
                .iter()
                .zip(arnoldi_vector.iter())
                .map(|(lhs, rhs)| lhs.conj() * rhs)
                .sum::<Complex64>();
            hessenberg[[basis_col, column]] = hessenberg_entry;
            for row in 0..dimension {
                arnoldi_vector[row] -= hessenberg_entry * basis[[row, basis_col]];
            }
        }

        let arnoldi_norm = vector_norm_complex(&arnoldi_vector);
        hessenberg[[column + 1, column]] = Complex64::new(arnoldi_norm, 0.0);
        if arnoldi_norm <= tolerance {
            effective_krylov_dim = column + 1;
            break;
        }
        for row in 0..dimension {
            basis[[row, column + 1]] = arnoldi_vector[row] / arnoldi_norm;
        }
    }

    let hessenberg_block =
        hessenberg.slice(ndarray::s![..(effective_krylov_dim + 1), ..effective_krylov_dim]);
    let hessenberg_conj_t = hessenberg_block.mapv(|value| value.conj()).reversed_axes();
    let normal_matrix = hessenberg_conj_t.dot(&hessenberg_block);

    let mut least_squares_rhs = Array1::<Complex64>::zeros(effective_krylov_dim + 1);
    least_squares_rhs[0] = Complex64::new(beta, 0.0);
    let normal_rhs = hessenberg_conj_t.dot(&least_squares_rhs);

    let least_squares_solution =
        lu::solve_complex(&normal_matrix, &normal_rhs).map_err(|_| IterativeError::Breakdown)?;
    output.fill(Complex64::default());
    for column in 0..effective_krylov_dim {
        let coefficient = least_squares_solution[column];
        for row in 0..dimension {
            output[row] += basis[[row, column]] * coefficient;
        }
    }

    let residual = matrix_b - &matrix_a.dot(&output.view());
    if vector_norm_complex(&residual) <= tolerance {
        Ok(())
    } else {
        Err(IterativeError::MaxIterationsExceeded)
    }
}

#[cfg(test)]
mod tests {
    use ndarray::{Array1, Array2};
    use num_complex::Complex64;

    use super::*;

    #[test]
    fn cg_solves_spd_system() {
        let matrix = Array2::from_shape_vec((2, 2), vec![4.0_f64, 1.0, 1.0, 3.0]).unwrap();
        let rhs = Array1::from_vec(vec![1.0_f64, 2.0]);
        let solution =
            conjugate_gradient(&matrix, &rhs, &IterativeConfig::<f64>::default()).unwrap();
        let reconstructed = matrix.dot(&solution);
        assert!((reconstructed[0] - rhs[0]).abs() < 1e-8);
        assert!((reconstructed[1] - rhs[1]).abs() < 1e-8);
    }

    #[test]
    fn gmres_solves_small_system() {
        let matrix = Array2::from_shape_vec((2, 2), vec![3.0_f64, 1.0, 1.0, 2.0]).unwrap();
        let rhs = Array1::from_vec(vec![9.0_f64, 8.0]);
        let solution = gmres(&matrix, &rhs, &IterativeConfig::<f64>::default()).unwrap();
        let reconstructed = matrix.dot(&solution);
        assert!((reconstructed[0] - rhs[0]).abs() < 1e-8);
        assert!((reconstructed[1] - rhs[1]).abs() < 1e-8);
    }

    #[test]
    fn real_f32_solvers_work() {
        let matrix = Array2::from_shape_vec((2, 2), vec![4.0_f32, 1.0, 1.0, 3.0]).unwrap();
        let rhs = Array1::from_vec(vec![1.0_f32, 2.0]);
        let config = IterativeConfig::<f32>::default();

        let cg = conjugate_gradient(&matrix, &rhs, &config).unwrap();
        let gm = gmres(&matrix, &rhs, &config).unwrap();

        let cg_reconstructed = matrix.dot(&cg);
        let gm_reconstructed = matrix.dot(&gm);
        for i in 0..rhs.len() {
            assert!((cg_reconstructed[i] - rhs[i]).abs() < 1e-4);
            assert!((gm_reconstructed[i] - rhs[i]).abs() < 1e-4);
        }
    }

    #[test]
    fn iterative_into_variants_reuse_output_buffers() {
        let spd = Array2::from_shape_vec((2, 2), vec![4.0_f64, 1.0, 1.0, 3.0]).unwrap();
        let rhs_spd = Array1::from_vec(vec![1.0_f64, 2.0]);
        let general = Array2::from_shape_vec((2, 2), vec![3.0_f64, 1.0, 1.0, 2.0]).unwrap();
        let rhs_general = Array1::from_vec(vec![9.0_f64, 8.0]);
        let config = IterativeConfig::<f64>::default();

        let mut cg_out = Array1::from_vec(vec![99.0_f64, 99.0]);
        let mut gmres_out = Array1::from_vec(vec![99.0_f64, 99.0]);

        conjugate_gradient_into(&spd, &rhs_spd, &config, &mut cg_out).unwrap();
        gmres_into(&general, &rhs_general, &config, &mut gmres_out).unwrap();

        let cg_reconstructed = spd.dot(&cg_out);
        let gmres_reconstructed = general.dot(&gmres_out);
        for i in 0..rhs_spd.len() {
            assert!((cg_reconstructed[i] - rhs_spd[i]).abs() < 1e-8);
        }
        for i in 0..rhs_general.len() {
            assert!((gmres_reconstructed[i] - rhs_general[i]).abs() < 1e-8);
        }
    }

    #[test]
    fn cg_rejects_dimension_mismatch() {
        let matrix = Array2::<f64>::eye(2);
        let rhs = Array1::from_vec(vec![1.0_f64, 2.0, 3.0]);
        let result = conjugate_gradient(&matrix, &rhs, &IterativeConfig::<f64>::default());
        assert!(matches!(result, Err(IterativeError::DimensionMismatch)));
    }

    #[test]
    fn iterative_into_rejects_bad_output_length() {
        let matrix = Array2::<f64>::eye(2);
        let rhs = Array1::from_vec(vec![1.0_f64, 2.0]);
        let config = IterativeConfig::<f64>::default();
        let mut bad_output = Array1::<f64>::zeros(3);

        let cg = conjugate_gradient_into(&matrix, &rhs, &config, &mut bad_output);
        let gmres_result = gmres_into(&matrix, &rhs, &config, &mut bad_output);

        assert!(matches!(cg, Err(IterativeError::DimensionMismatch)));
        assert!(matches!(gmres_result, Err(IterativeError::DimensionMismatch)));
    }

    #[test]
    fn gmres_rejects_empty_input() {
        let matrix = Array2::<f64>::zeros((0, 0));
        let rhs = Array1::<f64>::zeros(0);
        let result = gmres(&matrix, &rhs, &IterativeConfig::<f64>::default());
        assert!(matches!(result, Err(IterativeError::EmptyMatrix)));
    }

    #[test]
    fn cg_returns_zero_for_zero_rhs() {
        let matrix = Array2::<f64>::eye(2);
        let rhs = Array1::from_vec(vec![0.0_f64, 0.0]);
        let solution =
            conjugate_gradient(&matrix, &rhs, &IterativeConfig::<f64>::default()).unwrap();
        assert!(solution.iter().all(|value| value.abs() < 1e-12_f64));
    }

    #[test]
    fn cg_complex_solves_hermitian_spd_system() {
        let matrix = Array2::from_shape_vec((2, 2), vec![
            Complex64::new(4.0, 0.0),
            Complex64::new(1.0, 1.0),
            Complex64::new(1.0, -1.0),
            Complex64::new(3.0, 0.0),
        ])
        .unwrap();
        let rhs = Array1::from_vec(vec![Complex64::new(1.0, 0.5), Complex64::new(2.0, -1.0)]);
        let solution =
            conjugate_gradient_complex(&matrix, &rhs, &IterativeConfig::default()).unwrap();
        let reconstructed = matrix.dot(&solution);
        for i in 0..rhs.len() {
            assert!((reconstructed[i] - rhs[i]).norm() < 1e-7);
        }
    }

    #[test]
    fn gmres_complex_solves_small_system() {
        let matrix = Array2::from_shape_vec((2, 2), vec![
            Complex64::new(3.0, 1.0),
            Complex64::new(1.0, -0.5),
            Complex64::new(0.5, 1.0),
            Complex64::new(2.0, -1.0),
        ])
        .unwrap();
        let rhs = Array1::from_vec(vec![Complex64::new(1.0, 2.0), Complex64::new(3.0, -1.0)]);
        let solution = gmres_complex(&matrix, &rhs, &IterativeConfig::default()).unwrap();
        let reconstructed = matrix.dot(&solution);
        for i in 0..rhs.len() {
            assert!((reconstructed[i] - rhs[i]).norm() < 1e-7);
        }
    }

    #[test]
    fn complex_iterative_into_variants_reuse_output_buffers() {
        let matrix = Array2::from_shape_vec((2, 2), vec![
            Complex64::new(4.0, 0.0),
            Complex64::new(1.0, 1.0),
            Complex64::new(1.0, -1.0),
            Complex64::new(3.0, 0.0),
        ])
        .unwrap();
        let rhs = Array1::from_vec(vec![Complex64::new(1.0, 0.5), Complex64::new(2.0, -1.0)]);
        let general = Array2::from_shape_vec((2, 2), vec![
            Complex64::new(3.0, 1.0),
            Complex64::new(1.0, -0.5),
            Complex64::new(0.5, 1.0),
            Complex64::new(2.0, -1.0),
        ])
        .unwrap();
        let general_rhs =
            Array1::from_vec(vec![Complex64::new(1.0, 2.0), Complex64::new(3.0, -1.0)]);
        let config = IterativeConfig::default();

        let mut cg_out = Array1::from_vec(vec![Complex64::new(99.0, 0.0); 2]);
        let mut gmres_out = Array1::from_vec(vec![Complex64::new(99.0, 0.0); 2]);

        conjugate_gradient_complex_into(&matrix, &rhs, &config, &mut cg_out).unwrap();
        gmres_complex_into(&general, &general_rhs, &config, &mut gmres_out).unwrap();

        let cg_reconstructed = matrix.dot(&cg_out);
        let gmres_reconstructed = general.dot(&gmres_out);
        for i in 0..rhs.len() {
            assert!((cg_reconstructed[i] - rhs[i]).norm() < 1e-7);
            assert!((gmres_reconstructed[i] - general_rhs[i]).norm() < 1e-7);
        }
    }

    #[test]
    fn cg_complex_rejects_dimension_mismatch() {
        let matrix = Array2::from_shape_vec((2, 2), vec![
            Complex64::new(1.0, 0.0),
            Complex64::new(0.0, 0.0),
            Complex64::new(0.0, 0.0),
            Complex64::new(1.0, 0.0),
        ])
        .unwrap();
        let rhs = Array1::from_vec(vec![Complex64::new(1.0, 0.0)]);
        let result = conjugate_gradient_complex(&matrix, &rhs, &IterativeConfig::default());
        assert!(matches!(result, Err(IterativeError::DimensionMismatch)));
    }

    #[test]
    fn gmres_complex_rejects_empty_input() {
        let matrix = Array2::<Complex64>::zeros((0, 0));
        let rhs = Array1::<Complex64>::zeros(0);
        let result = gmres_complex(&matrix, &rhs, &IterativeConfig::default());
        assert!(matches!(result, Err(IterativeError::EmptyMatrix)));
    }
}
