|
"""Abstract linear algebra library.
This module defines a class hierarchy that implements a kind of "lazy" matrix representation, called the ``LinearOperator``. It can be used to do linear algebra with extremely large sparse or structured matrices, without representing those explicitly in memory. Such matrices can be added, multiplied, transposed, etc.
As a motivating example, suppose you want have a matrix where almost all of the elements have the value one. The standard sparse matrix representation skips the storage of zeros, but not ones. By contrast, a LinearOperator is able to represent such matrices efficiently. First, we need a compact way to represent an all-ones matrix::
>>> import numpy as np >>> class Ones(LinearOperator): ... def __init__(self, shape): ... super(Ones, self).__init__(dtype=None, shape=shape) ... def _matvec(self, x): ... return np.repeat(x.sum(), self.shape[0])
Instances of this class emulate ``np.ones(shape)``, but using a constant amount of storage, independent of ``shape``. The ``_matvec`` method specifies how this linear operator multiplies with (operates on) a vector. We can now add this operator to a sparse matrix that stores only offsets from one::
>>> from scipy.sparse import csr_matrix >>> offsets = csr_matrix([[1, 0, 2], [0, -1, 0], [0, 0, 3]]) >>> A = aslinearoperator(offsets) + Ones(offsets.shape) >>> A.dot([1, 2, 3]) array([13, 4, 15])
The result is the same as that given by its dense, explicitly-stored counterpart::
>>> (np.ones(A.shape, A.dtype) + offsets.toarray()).dot([1, 2, 3]) array([13, 4, 15])
Several algorithms in the ``scipy.sparse`` library are able to operate on ``LinearOperator`` instances. """
"""Common interface for performing matrix vector products
Many iterative methods (e.g. cg, gmres) do not need to know the individual entries of a matrix to solve a linear system A*x=b. Such solvers only require the computation of matrix vector products, A*v where v is a dense vector. This class serves as an abstract interface between iterative solvers and matrix-like objects.
To construct a concrete LinearOperator, either pass appropriate callables to the constructor of this class, or subclass it.
A subclass must implement either one of the methods ``_matvec`` and ``_matmat``, and the attributes/properties ``shape`` (pair of integers) and ``dtype`` (may be None). It may call the ``__init__`` on this class to have these attributes validated. Implementing ``_matvec`` automatically implements ``_matmat`` (using a naive algorithm) and vice-versa.
Optionally, a subclass may implement ``_rmatvec`` or ``_adjoint`` to implement the Hermitian adjoint (conjugate transpose). As with ``_matvec`` and ``_matmat``, implementing either ``_rmatvec`` or ``_adjoint`` implements the other automatically. Implementing ``_adjoint`` is preferable; ``_rmatvec`` is mostly there for backwards compatibility.
Parameters ---------- shape : tuple Matrix dimensions (M,N). matvec : callable f(v) Returns returns A * v. rmatvec : callable f(v) Returns A^H * v, where A^H is the conjugate transpose of A. matmat : callable f(V) Returns A * V, where V is a dense matrix with dimensions (N,K). dtype : dtype Data type of the matrix.
Attributes ---------- args : tuple For linear operators describing products etc. of other linear operators, the operands of the binary operation.
See Also -------- aslinearoperator : Construct LinearOperators
Notes ----- The user-defined matvec() function must properly handle the case where v has shape (N,) as well as the (N,1) case. The shape of the return type is handled internally by LinearOperator.
LinearOperator instances can also be multiplied, added with each other and exponentiated, all lazily: the result of these operations is always a new, composite LinearOperator, that defers linear operations to the original operators and combines the results.
Examples -------- >>> import numpy as np >>> from scipy.sparse.linalg import LinearOperator >>> def mv(v): ... return np.array([2*v[0], 3*v[1]]) ... >>> A = LinearOperator((2,2), matvec=mv) >>> A <2x2 _CustomLinearOperator with dtype=float64> >>> A.matvec(np.ones(2)) array([ 2., 3.]) >>> A * np.ones(2) array([ 2., 3.])
""" if cls is LinearOperator: # Operate as _CustomLinearOperator factory. return super(LinearOperator, cls).__new__(_CustomLinearOperator) else: obj = super(LinearOperator, cls).__new__(cls)
if (type(obj)._matvec == LinearOperator._matvec and type(obj)._matmat == LinearOperator._matmat): raise TypeError("LinearOperator subclass should implement" " at least one of _matvec and _matmat.")
return obj
"""Initialize this LinearOperator.
To be called by subclasses. ``dtype`` may be None; ``shape`` should be convertible to a length-2 tuple. """ if dtype is not None: dtype = np.dtype(dtype)
shape = tuple(shape) if not isshape(shape): raise ValueError("invalid shape %r (must be 2-d)" % (shape,))
self.dtype = dtype self.shape = shape
"""Called from subclasses at the end of the __init__ routine. """ if self.dtype is None: v = np.zeros(self.shape[-1]) self.dtype = np.asarray(self.matvec(v)).dtype
"""Default matrix-matrix multiplication handler.
Falls back on the user-defined _matvec method, so defining that will define matrix multiplication (though in a very suboptimal way). """
return np.hstack([self.matvec(col.reshape(-1,1)) for col in X.T])
"""Default matrix-vector multiplication handler.
If self is a linear operator of shape (M, N), then this method will be called on a shape (N,) or (N, 1) ndarray, and should return a shape (M,) or (M, 1) ndarray.
This default implementation falls back on _matmat, so defining that will define matrix-vector multiplication as well. """ return self.matmat(x.reshape(-1, 1))
"""Matrix-vector multiplication.
Performs the operation y=A*x where A is an MxN linear operator and x is a column vector or 1-d array.
Parameters ---------- x : {matrix, ndarray} An array with shape (N,) or (N,1).
Returns ------- y : {matrix, ndarray} A matrix or ndarray with shape (M,) or (M,1) depending on the type and shape of the x argument.
Notes ----- This matvec wraps the user-specified matvec routine or overridden _matvec method to ensure that y has the correct shape and type.
"""
x = np.asanyarray(x)
M,N = self.shape
if x.shape != (N,) and x.shape != (N,1): raise ValueError('dimension mismatch')
y = self._matvec(x)
if isinstance(x, np.matrix): y = asmatrix(y) else: y = np.asarray(y)
if x.ndim == 1: y = y.reshape(M) elif x.ndim == 2: y = y.reshape(M,1) else: raise ValueError('invalid shape returned by user-defined matvec()')
return y
"""Adjoint matrix-vector multiplication.
Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array.
Parameters ---------- x : {matrix, ndarray} An array with shape (M,) or (M,1).
Returns ------- y : {matrix, ndarray} A matrix or ndarray with shape (N,) or (N,1) depending on the type and shape of the x argument.
Notes ----- This rmatvec wraps the user-specified rmatvec routine or overridden _rmatvec method to ensure that y has the correct shape and type.
"""
x = np.asanyarray(x)
M,N = self.shape
if x.shape != (M,) and x.shape != (M,1): raise ValueError('dimension mismatch')
y = self._rmatvec(x)
if isinstance(x, np.matrix): y = asmatrix(y) else: y = np.asarray(y)
if x.ndim == 1: y = y.reshape(N) elif x.ndim == 2: y = y.reshape(N,1) else: raise ValueError('invalid shape returned by user-defined rmatvec()')
return y
"""Default implementation of _rmatvec; defers to adjoint.""" if type(self)._adjoint == LinearOperator._adjoint: # _adjoint not overridden, prevent infinite recursion raise NotImplementedError else: return self.H.matvec(x)
"""Matrix-matrix multiplication.
Performs the operation y=A*X where A is an MxN linear operator and X dense N*K matrix or ndarray.
Parameters ---------- X : {matrix, ndarray} An array with shape (N,K).
Returns ------- Y : {matrix, ndarray} A matrix or ndarray with shape (M,K) depending on the type of the X argument.
Notes ----- This matmat wraps any user-specified matmat routine or overridden _matmat method to ensure that y has the correct type.
"""
X = np.asanyarray(X)
if X.ndim != 2: raise ValueError('expected 2-d ndarray or matrix, not %d-d' % X.ndim)
M,N = self.shape
if X.shape[0] != N: raise ValueError('dimension mismatch: %r, %r' % (self.shape, X.shape))
Y = self._matmat(X)
if isinstance(Y, np.matrix): Y = asmatrix(Y)
return Y
return self*x
return self.dot(x)
"""Matrix-matrix or matrix-vector multiplication.
Parameters ---------- x : array_like 1-d or 2-d array, representing a vector or matrix.
Returns ------- Ax : array 1-d or 2-d array (depending on the shape of x) that represents the result of applying this linear operator on x.
""" if isinstance(x, LinearOperator): return _ProductLinearOperator(self, x) elif np.isscalar(x): return _ScaledLinearOperator(self, x) else: x = np.asarray(x)
if x.ndim == 1 or x.ndim == 2 and x.shape[1] == 1: return self.matvec(x) elif x.ndim == 2: return self.matmat(x) else: raise ValueError('expected 1-d or 2-d array or matrix, got %r' % x)
if np.isscalar(other): raise ValueError("Scalar operands are not allowed, " "use '*' instead") return self.__mul__(other)
if np.isscalar(other): raise ValueError("Scalar operands are not allowed, " "use '*' instead") return self.__rmul__(other)
if np.isscalar(x): return _ScaledLinearOperator(self, x) else: return NotImplemented
if np.isscalar(p): return _PowerLinearOperator(self, p) else: return NotImplemented
if isinstance(x, LinearOperator): return _SumLinearOperator(self, x) else: return NotImplemented
return _ScaledLinearOperator(self, -1)
return self.__add__(-x)
def __repr__(self): M,N = self.shape if self.dtype is None: dt = 'unspecified dtype' else: dt = 'dtype=' + str(self.dtype)
return '<%dx%d %s with %s>' % (M, N, self.__class__.__name__, dt)
"""Hermitian adjoint.
Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.
Can be abbreviated self.H instead of self.adjoint().
Returns ------- A_H : LinearOperator Hermitian adjoint of self. """ return self._adjoint()
"""Transpose this linear operator.
Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose(). """ return self._transpose()
"""Default implementation of _adjoint; defers to rmatvec.""" shape = (self.shape[1], self.shape[0]) return _CustomLinearOperator(shape, matvec=self.rmatvec, rmatvec=self.matvec, dtype=self.dtype)
"""Linear operator defined in terms of user-specified operations."""
super(_CustomLinearOperator, self).__init__(dtype, shape)
self.args = ()
self.__matvec_impl = matvec self.__rmatvec_impl = rmatvec self.__matmat_impl = matmat
self._init_dtype()
if self.__matmat_impl is not None: return self.__matmat_impl(X) else: return super(_CustomLinearOperator, self)._matmat(X)
return self.__matvec_impl(x)
func = self.__rmatvec_impl if func is None: raise NotImplementedError("rmatvec is not defined") return self.__rmatvec_impl(x)
return _CustomLinearOperator(shape=(self.shape[1], self.shape[0]), matvec=self.__rmatvec_impl, rmatvec=self.__matvec_impl, dtype=self.dtype)
if dtypes is None: dtypes = [] for obj in operators: if obj is not None and hasattr(obj, 'dtype'): dtypes.append(obj.dtype) return np.find_common_type(dtypes, [])
if not isinstance(A, LinearOperator) or \ not isinstance(B, LinearOperator): raise ValueError('both operands have to be a LinearOperator') if A.shape != B.shape: raise ValueError('cannot add %r and %r: shape mismatch' % (A, B)) self.args = (A, B) super(_SumLinearOperator, self).__init__(_get_dtype([A, B]), A.shape)
return self.args[0].matvec(x) + self.args[1].matvec(x)
return self.args[0].rmatvec(x) + self.args[1].rmatvec(x)
return self.args[0].matmat(x) + self.args[1].matmat(x)
A, B = self.args return A.H + B.H
if not isinstance(A, LinearOperator) or \ not isinstance(B, LinearOperator): raise ValueError('both operands have to be a LinearOperator') if A.shape[1] != B.shape[0]: raise ValueError('cannot multiply %r and %r: shape mismatch' % (A, B)) super(_ProductLinearOperator, self).__init__(_get_dtype([A, B]), (A.shape[0], B.shape[1])) self.args = (A, B)
return self.args[0].matvec(self.args[1].matvec(x))
return self.args[1].rmatvec(self.args[0].rmatvec(x))
return self.args[0].matmat(self.args[1].matmat(x))
A, B = self.args return B.H * A.H
if not isinstance(A, LinearOperator): raise ValueError('LinearOperator expected as A') if not np.isscalar(alpha): raise ValueError('scalar expected as alpha') dtype = _get_dtype([A], [type(alpha)]) super(_ScaledLinearOperator, self).__init__(dtype, A.shape) self.args = (A, alpha)
return self.args[1] * self.args[0].matvec(x)
return np.conj(self.args[1]) * self.args[0].rmatvec(x)
return self.args[1] * self.args[0].matmat(x)
A, alpha = self.args return A.H * alpha
if not isinstance(A, LinearOperator): raise ValueError('LinearOperator expected as A') if A.shape[0] != A.shape[1]: raise ValueError('square LinearOperator expected, got %r' % A) if not isintlike(p) or p < 0: raise ValueError('non-negative integer expected as p')
super(_PowerLinearOperator, self).__init__(_get_dtype([A]), A.shape) self.args = (A, p)
res = np.array(x, copy=True) for i in range(self.args[1]): res = fun(res) return res
return self._power(self.args[0].matvec, x)
return self._power(self.args[0].rmatvec, x)
return self._power(self.args[0].matmat, x)
A, p = self.args return A.H ** p
super(MatrixLinearOperator, self).__init__(A.dtype, A.shape) self.A = A self.__adj = None self.args = (A,)
return self.A.dot(X)
if self.__adj is None: self.__adj = _AdjointMatrixOperator(self) return self.__adj
self.A = adjoint.A.T.conj() self.__adjoint = adjoint self.args = (adjoint,) self.shape = adjoint.shape[1], adjoint.shape[0]
def dtype(self): return self.__adjoint.dtype
return self.__adjoint
super(IdentityOperator, self).__init__(dtype, shape)
return x
return x
return x
return self
"""Return A as a LinearOperator.
'A' may be any of the following types: - ndarray - matrix - sparse matrix (e.g. csr_matrix, lil_matrix, etc.) - LinearOperator - An object with .shape and .matvec attributes
See the LinearOperator documentation for additional information.
Notes ----- If 'A' has no .dtype attribute, the data type is determined by calling :func:`LinearOperator.matvec()` - set the .dtype attribute to prevent this call upon the linear operator creation.
Examples -------- >>> from scipy.sparse.linalg import aslinearoperator >>> M = np.array([[1,2,3],[4,5,6]], dtype=np.int32) >>> aslinearoperator(M) <2x3 MatrixLinearOperator with dtype=int32> """ if isinstance(A, LinearOperator): return A
elif isinstance(A, np.ndarray) or isinstance(A, np.matrix): if A.ndim > 2: raise ValueError('array must have ndim <= 2') A = np.atleast_2d(np.asarray(A)) return MatrixLinearOperator(A)
elif isspmatrix(A): return MatrixLinearOperator(A)
else: if hasattr(A, 'shape') and hasattr(A, 'matvec'): rmatvec = None dtype = None
if hasattr(A, 'rmatvec'): rmatvec = A.rmatvec if hasattr(A, 'dtype'): dtype = A.dtype return LinearOperator(A.shape, A.matvec, rmatvec=rmatvec, dtype=dtype)
else: raise TypeError('type not understood') |