ParaMonte Fortran 2.0.0
Parallel Monte Carlo and Machine Learning Library
See the latest version documentation. |
This module contains procedures and generic interfaces relevant to arbitrary-rank updates to vectors, general matrices, or Symmetric/Hermitian triangular matrices of type integer
, complex
, and real
of arbitrary type-kind parameters.
More...
Data Types | |
interface | setMatUpdate |
Return the result of arbitrary-rank Symmetric/Hermitian updates to triangular matrices of type integer , complex , and real of arbitrary type-kind parameters. More... | |
interface | setMatUpdateR1 |
Return the rank-1 update of the input matrix mat using the input vectors vecA and vecB . More... | |
interface | setMatUpdateTriang |
Return the result of arbitrary-rank Symmetric/Hermitian updates to triangular matrices of type integer , complex , and real of arbitrary type-kind parameters. More... | |
Variables | |
character(*, SK), parameter | MODULE_NAME = "@pm_matrixUpdate" |
This module contains procedures and generic interfaces relevant to arbitrary-rank updates to vectors, general matrices, or Symmetric/Hermitian triangular matrices of type integer
, complex
, and real
of arbitrary type-kind parameters.
Let \(\ms{matA}\) be a \(n\times n\) matrix and \(\ms{vecA}\) and \(\ms{vecB}\) two \(n\times 1\) column vectors.
The following transformation is called a rank one update to \(\ms{matA}\),
\begin{equation} \ms{matA} := \ms{matA} + \alpha \ms{vecA}~\ms{vecB}^\mathrm{T} ~, \end{equation}
where \(\alpha\) is an arbitrary scalar.
For complex matrices, the transformation can be also done as the following,
\begin{equation} \ms{matA} := \ms{matA} + \alpha \ms{vecA}~\ms{vecB}^\mathrm{H} ~, \end{equation}
where \(\mathrm{H}\) denotes the Hermitian (or conjugate or Adjoint) transpose operation.
Motivation: Sherman-Morrison formula
The Rank One Update transform offers a fast method of indirectly computing the inverse of an update matrix.
In mathematics, in particular linear algebra, the Sherman–Morrison formula, named after Jack Sherman and Winifred J. Morrison, computes the inverse of the sum of an invertible matrix \(\ms{matA}\) and the outer product, \(\ms{vecA}~\ms{vecB}^{\mathrm{T}}\), of vectors \(\ms{vecA}\) and \(\ms{vecB}\).
Suppose \(\ms{matA} \in \mathbb{R}^{n\times n}\) is an invertible square matrix and \(\ms{vecA}, \ms{vecB}\in \mathbb{R}^{n}\) are column vectors.
Then \(\ms{matA} + \ms{vecA}~\ms{vecB}^{\mathrm{T}}\) is invertible if and only if \(1 + \ms{vecB}^{\mathrm{T}} \ms{matA}^{-1} \ms{vecA} \neq 0\).
In this case,
\begin{equation} \left(\ms{matA} + \ms{vecA}~\ms{vecB}^{\textsf{T}}\right)^{-1} = \ms{matA}^{-1} - \frac{\ms{matA}^{-1} \ms{vecA}~\ms{vecB}^{\textsf{T}}\ms{matA}^{-1}} {1 + \ms{vecB}^{\textsf{T}}\ms{matA}^{-1}\ms{vecA}} ~. \end{equation}
Here, \(\ms{vecA}~\ms{vecB}^{\textsf{T}}\) is thSe outer product of two vectors \(\ms{vecA}\) and \(\ms{vecB}\).
The Sherman-Morrison formula offers computationally efficient way of computing the inverse of an updated matrix when the original inverse \(\ms{matA}^{-1}\) is already available.
The computational complexity of a full recomputation of the inverse is \(n^{3}\) as opposed to \(n^{2}\) via the Sherman-Morrison formula.
The difference in computational complexity is particularly relevant for high-dimensional matrices.
The procedures under the generic interface setMatUpdateTriang return the result of arbitrary-rank Symmetric/Hermitian updates to triangular matrices in one of the following forms,
\begin{align*} & \ms{mat} \leftarrow \alpha \ms{matA}~~ \ms{matA}^T + \beta \ms{mat} \\ & \ms{mat} \leftarrow \alpha \ms{matA}^T \ms{matA}~~ + \beta \ms{mat} \\ & \ms{mat} \leftarrow \alpha \ms{matA}~~ \ms{matA}^H + \beta \ms{mat} \\ & \ms{mat} \leftarrow \alpha \ms{matA}^H \ms{matA}~~ + \beta \ms{mat} \end{align*}
where \(\cdot^T\) and \(\cdot^H\) represent Symmetric and Hermitian transpositions respectively.
Because the output matrix \(\ms{mat}\) is Symmetric/Hermitian, only the upper or the lower triangles need to be computed.
SSHRK
, DSHRK
, CSHRK
, ZSHRK
.SGER
, DGER
, CGERU
, ZGERU
, CGERC
, and ZGERC
.SSYRK
, DSYRK
, CSYRK
, ZSYRK
, CHERK
, and ZHERK
.integer
of arbitrary kinds.
Final Remarks ⛓
If you believe this algorithm or its documentation can be improved, we appreciate your contribution and help to edit this page's documentation and source file on GitHub.
For details on the naming abbreviations, see this page.
For details on the naming conventions, see this page.
This software is distributed under the MIT license with additional terms outlined below.
This software is available to the public under a highly permissive license.
Help us justify its continued development and maintenance by acknowledging its benefit to society, distributing it, and contributing to it.
character(*, SK), parameter pm_matrixUpdate::MODULE_NAME = "@pm_matrixUpdate" |
Definition at line 130 of file pm_matrixUpdate.F90.