-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Sparse matrix linear-equation solver
--   
--   Sparse matrix linear-equation solver, using the conjugate gradient
--   algorithm. Note that the technique only applies to matrices that are:
--   
--   <ul>
--   <li>Symmetric</li>
--   <li>Positive-definite</li>
--   </ul>
--   
--   See <a>http://en.wikipedia.org/wiki/Conjugate_gradient_method</a> for
--   details.
--   
--   The conjugate gradient method can handle very large sparse matrices,
--   where direct methods (such as LU decomposition) are way too expensive
--   to be useful in practice.
@package conjugateGradient
@version 1.0


-- | (The linear equation solver library is hosted at
--   <a>http://github.com/LeventErkok/conjugateGradient</a>. Comments, bug
--   reports, and patches are always welcome.)
--   
--   Sparse matrix linear-equation solver, using the conjugate gradient
--   algorithm. Note that the technique only applies to matrices that are:
--   
--   <ul>
--   <li>Symmetric</li>
--   <li>Positive-definite</li>
--   </ul>
--   
--   See <a>http://en.wikipedia.org/wiki/Conjugate_gradient_method</a> for
--   details.
--   
--   The conjugate gradient method can handle very large sparse matrices,
--   where direct methods (such as LU decomposition) are way too expensive
--   to be useful in practice.
module Math.ConjugateGradient

-- | A sparse vector containing elements of type <tt>a</tt>. (For our
--   purposes, the elements will be either <a>Float</a>s or
--   <a>Double</a>s.)
type SV a = IntMap a

-- | A sparse matrix is an int-map containing sparse row-vectors. Again,
--   only put in rows that have a non-<tt>0</tt> element in them for
--   efficiency.
type SM a = IntMap (SV a)

-- | Multiply a sparse-vector by a scalar.
sMulSV :: RealFloat a => a -> SV a -> SV a

-- | Multiply a sparse-matrix by a scalar.
sMulSM :: RealFloat a => a -> SM a -> SM a

-- | Add two sparse vectors.
addSV :: RealFloat a => SV a -> SV a -> SV a

-- | Subtract two sparse vectors.
subSV :: RealFloat a => SV a -> SV a -> SV a

-- | Dot product of two sparse vectors.
dotSV :: RealFloat a => SV a -> SV a -> a

-- | Multiply a sparse matrix (nxn) with a sparse vector (nx1), obtaining a
--   sparse vector (nx1).
mulSMV :: RealFloat a => SM a -> SV a -> SV a

-- | Norm of a sparse vector. (Square-root of it's dot-product with
--   itself.)
normSV :: RealFloat a => SV a -> a

-- | Conjugate Gradient Solver for the system <tt>Ax=b</tt>. See:
--   <a>http://en.wikipedia.org/wiki/Conjugate_gradient_method</a>.
--   
--   NB. Assumptions on the input:
--   
--   <ul>
--   <li>The <tt>A</tt> matrix is symmetric and positive definite.</li>
--   <li>The indices start from <tt>0</tt> and go consecutively up-to
--   <tt>n-1</tt>. (Only non-<tt>0</tt> value/row indices has to be
--   present, of course.)</li>
--   </ul>
--   
--   For efficiency reasons, we do not check for either property. (If these
--   assumptions are violated, the algorithm will still produce a result,
--   but not the one you expected!)
--   
--   We perform either <tt>10^6</tt> iterations of the Conjugate-Gradient
--   algorithm, or until the error factor is less than <tt>1e-10</tt>. The
--   error factor is defined as the difference of the norm of the current
--   solution from the last one, as we go through the iteration. See
--   <a>http://en.wikipedia.org/wiki/Conjugate_gradient_method#Convergence_properties_of_the_conjugate_gradient_method</a>
--   for a discussion on the convergence properties of this algorithm.
solveCG :: (RandomGen g, RealFloat a, Random a) => g -> Int -> SM a -> SV a -> (a, SV a)

-- | Display a solution in a human-readable form. Needless to say, only use
--   this method when the system is small enough to fit nicely on the
--   screen.
showSolution :: RealFloat a => Int -> Int -> Int -> SM a -> SV a -> SV a -> String