ParaMonte Fortran 2.0.0
Parallel Monte Carlo and Machine Learning Library
See the latest version documentation.
pm_matrixUpdate Module Reference

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"
 

Detailed Description

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.

Rank-1 matrix update

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.

Note
The rank one name of the transformation stems from the fact that the rank of the \(n \times n\) matrix \(\ms{vecA}~\ms{vecB}^{T}\) is equal to \(1\).
This is because a single vector, \(\ms{vecA}\), spans all the columns of \(\ms{vecA}~\ms{vecB}^{T}\).

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.

Triangular matrix update

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.

See also
netlib::LAPACK
The IBM Engineering and Scientific Subroutine Library.
Developer Reference for Intel® oneAPI Math Kernel Library - Fortran.
Dongarra, J. J.; DuCroz, J.; Hammarling, S.; Hanson, R. J. March 1988. An Extended Set of Fortran Basic Linear Algebra Subprograms. ACM Transactions on Mathematical Software , 14(1):1–17.
Remarks
The generic interfaces of this module dispatch to optimized BLAS libraries where available.
Otherwise, reference implementations of BLAS algorithms are used.
Warning
This module is still a work in progress.
However, all available interfaces and functions of this module are fully functional and tested.
But the interfaces may change over time as more functionalities are added.
In particular, the generic interfaces setMatUpdateR1 and setMatUpdateTriang will be merged with setMatUpdateR1 in future library releases.
BLAS/LAPACK equivalent:
The procedures under discussion combine, modernize, and extend the interface and functionalities of Version 3.11 of BLAS/LAPACK routine(s): SSHRK, DSHRK, CSHRK, ZSHRK.
SGER, DGER, CGERU, ZGERU, CGERC, and ZGERC.
SSYRK, DSYRK, CSYRK, ZSYRK, CHERK, and ZHERK.
Notably, the interfaces are also extended to support matrices of type integer of arbitrary kinds.
Test:
test_pm_matrixUpdateR
Todo:
Normal Priority: A benchmark comparison of the procedures of this module with the default BLAS/LAPACK implementation would be informative.
Todo:
Normal Priority: A benchmark comparison of the procedures of this module with the default BLAS/LAPACK implementation would be informative.


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.

  1. If you use any parts or concepts from this library to any extent, please acknowledge the usage by citing the relevant publications of the ParaMonte library.
  2. If you regenerate any parts/ideas from this library in a programming environment other than those currently supported by this ParaMonte library (i.e., other than C, C++, Fortran, MATLAB, Python, R), please also ask the end users to cite this original ParaMonte library.

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.

Author:
Fatemeh Bagheri, Tuesday 08:49 PM, August 10, 2021, Dallas, TX Amir Shahmoradi, Friday 1:54 AM, April 21, 2017, Institute for Computational Engineering and Sciences (ICES), The University of Texas, Austin, TX

Variable Documentation

◆ MODULE_NAME

character(*, SK), parameter pm_matrixUpdate::MODULE_NAME = "@pm_matrixUpdate"

Definition at line 130 of file pm_matrixUpdate.F90.