| |
| |
| |
| |
| |
|
|
| from warnings import warn |
| from itertools import product |
| import numpy as np |
| from numpy import atleast_1d, atleast_2d |
| from .lapack import get_lapack_funcs, _compute_lwork |
| from ._misc import LinAlgError, _datacopied, LinAlgWarning |
| from ._decomp import _asarray_validated |
| from . import _decomp, _decomp_svd |
| from ._solve_toeplitz import levinson |
| from ._cythonized_array_utils import find_det_from_lu |
| from scipy._lib.deprecation import _NoValue, _deprecate_positional_args |
|
|
| |
| from scipy.linalg._flinalg_py import get_flinalg_funcs |
|
|
| __all__ = ['solve', 'solve_triangular', 'solveh_banded', 'solve_banded', |
| 'solve_toeplitz', 'solve_circulant', 'inv', 'det', 'lstsq', |
| 'pinv', 'pinvh', 'matrix_balance', 'matmul_toeplitz'] |
|
|
|
|
| |
| |
| |
|
|
| |
| |
| |
| lapack_cast_dict = {x: ''.join([y for y in 'fdFD' if np.can_cast(x, y)]) |
| for x in np.typecodes['All']} |
|
|
|
|
| |
| def _solve_check(n, info, lamch=None, rcond=None): |
| """ Check arguments during the different steps of the solution phase """ |
| if info < 0: |
| raise ValueError(f'LAPACK reported an illegal value in {-info}-th argument.') |
| elif 0 < info: |
| raise LinAlgError('Matrix is singular.') |
|
|
| if lamch is None: |
| return |
| E = lamch('E') |
| if rcond < E: |
| warn(f'Ill-conditioned matrix (rcond={rcond:.6g}): ' |
| 'result may not be accurate.', |
| LinAlgWarning, stacklevel=3) |
|
|
|
|
| def solve(a, b, lower=False, overwrite_a=False, |
| overwrite_b=False, check_finite=True, assume_a='gen', |
| transposed=False): |
| """ |
| Solves the linear equation set ``a @ x == b`` for the unknown ``x`` |
| for square `a` matrix. |
| |
| If the data matrix is known to be a particular type then supplying the |
| corresponding string to ``assume_a`` key chooses the dedicated solver. |
| The available options are |
| |
| =================== ======== |
| generic matrix 'gen' |
| symmetric 'sym' |
| hermitian 'her' |
| positive definite 'pos' |
| =================== ======== |
| |
| If omitted, ``'gen'`` is the default structure. |
| |
| The datatype of the arrays define which solver is called regardless |
| of the values. In other words, even when the complex array entries have |
| precisely zero imaginary parts, the complex solver will be called based |
| on the data type of the array. |
| |
| Parameters |
| ---------- |
| a : (N, N) array_like |
| Square input data |
| b : (N, NRHS) array_like |
| Input data for the right hand side. |
| lower : bool, default: False |
| Ignored if ``assume_a == 'gen'`` (the default). If True, the |
| calculation uses only the data in the lower triangle of `a`; |
| entries above the diagonal are ignored. If False (default), the |
| calculation uses only the data in the upper triangle of `a`; entries |
| below the diagonal are ignored. |
| overwrite_a : bool, default: False |
| Allow overwriting data in `a` (may enhance performance). |
| overwrite_b : bool, default: False |
| Allow overwriting data in `b` (may enhance performance). |
| check_finite : bool, default: True |
| Whether to check that the input matrices contain only finite numbers. |
| Disabling may give a performance gain, but may result in problems |
| (crashes, non-termination) if the inputs do contain infinities or NaNs. |
| assume_a : str, {'gen', 'sym', 'her', 'pos'} |
| Valid entries are explained above. |
| transposed : bool, default: False |
| If True, solve ``a.T @ x == b``. Raises `NotImplementedError` |
| for complex `a`. |
| |
| Returns |
| ------- |
| x : (N, NRHS) ndarray |
| The solution array. |
| |
| Raises |
| ------ |
| ValueError |
| If size mismatches detected or input a is not square. |
| LinAlgError |
| If the matrix is singular. |
| LinAlgWarning |
| If an ill-conditioned input a is detected. |
| NotImplementedError |
| If transposed is True and input a is a complex matrix. |
| |
| Notes |
| ----- |
| If the input b matrix is a 1-D array with N elements, when supplied |
| together with an NxN input a, it is assumed as a valid column vector |
| despite the apparent size mismatch. This is compatible with the |
| numpy.dot() behavior and the returned result is still 1-D array. |
| |
| The generic, symmetric, Hermitian and positive definite solutions are |
| obtained via calling ?GESV, ?SYSV, ?HESV, and ?POSV routines of |
| LAPACK respectively. |
| |
| Examples |
| -------- |
| Given `a` and `b`, solve for `x`: |
| |
| >>> import numpy as np |
| >>> a = np.array([[3, 2, 0], [1, -1, 0], [0, 5, 1]]) |
| >>> b = np.array([2, 4, -1]) |
| >>> from scipy import linalg |
| >>> x = linalg.solve(a, b) |
| >>> x |
| array([ 2., -2., 9.]) |
| >>> np.dot(a, x) == b |
| array([ True, True, True], dtype=bool) |
| |
| """ |
| |
| b_is_1D = False |
|
|
| a1 = atleast_2d(_asarray_validated(a, check_finite=check_finite)) |
| b1 = atleast_1d(_asarray_validated(b, check_finite=check_finite)) |
| n = a1.shape[0] |
|
|
| overwrite_a = overwrite_a or _datacopied(a1, a) |
| overwrite_b = overwrite_b or _datacopied(b1, b) |
|
|
| if a1.shape[0] != a1.shape[1]: |
| raise ValueError('Input a needs to be a square matrix.') |
|
|
| if n != b1.shape[0]: |
| |
| if not (n == 1 and b1.size != 0): |
| raise ValueError('Input b has to have same number of rows as ' |
| 'input a') |
|
|
| |
| if b1.size == 0: |
| return np.asfortranarray(b1.copy()) |
|
|
| |
| if b1.ndim == 1: |
| if n == 1: |
| b1 = b1[None, :] |
| else: |
| b1 = b1[:, None] |
| b_is_1D = True |
|
|
| if assume_a not in ('gen', 'sym', 'her', 'pos'): |
| raise ValueError(f'{assume_a} is not a recognized matrix structure') |
|
|
| |
| |
| if assume_a == 'her' and not np.iscomplexobj(a1): |
| assume_a = 'sym' |
|
|
| |
| |
| |
| if a1.dtype.char in 'fF': |
| lamch = get_lapack_funcs('lamch', dtype='f') |
| else: |
| lamch = get_lapack_funcs('lamch', dtype='d') |
|
|
| |
| |
| |
| lange = get_lapack_funcs('lange', (a1,)) |
|
|
| |
| |
| |
| |
| if transposed: |
| trans = 1 |
| norm = 'I' |
| if np.iscomplexobj(a1): |
| raise NotImplementedError('scipy.linalg.solve can currently ' |
| 'not solve a^T x = b or a^H x = b ' |
| 'for complex matrices.') |
| else: |
| trans = 0 |
| norm = '1' |
|
|
| anorm = lange(norm, a1) |
|
|
| |
| if assume_a == 'gen': |
| gecon, getrf, getrs = get_lapack_funcs(('gecon', 'getrf', 'getrs'), |
| (a1, b1)) |
| lu, ipvt, info = getrf(a1, overwrite_a=overwrite_a) |
| _solve_check(n, info) |
| x, info = getrs(lu, ipvt, b1, |
| trans=trans, overwrite_b=overwrite_b) |
| _solve_check(n, info) |
| rcond, info = gecon(lu, anorm, norm=norm) |
| |
| elif assume_a == 'her': |
| hecon, hesv, hesv_lw = get_lapack_funcs(('hecon', 'hesv', |
| 'hesv_lwork'), (a1, b1)) |
| lwork = _compute_lwork(hesv_lw, n, lower) |
| lu, ipvt, x, info = hesv(a1, b1, lwork=lwork, |
| lower=lower, |
| overwrite_a=overwrite_a, |
| overwrite_b=overwrite_b) |
| _solve_check(n, info) |
| rcond, info = hecon(lu, ipvt, anorm) |
| |
| elif assume_a == 'sym': |
| sycon, sysv, sysv_lw = get_lapack_funcs(('sycon', 'sysv', |
| 'sysv_lwork'), (a1, b1)) |
| lwork = _compute_lwork(sysv_lw, n, lower) |
| lu, ipvt, x, info = sysv(a1, b1, lwork=lwork, |
| lower=lower, |
| overwrite_a=overwrite_a, |
| overwrite_b=overwrite_b) |
| _solve_check(n, info) |
| rcond, info = sycon(lu, ipvt, anorm) |
| |
| else: |
| pocon, posv = get_lapack_funcs(('pocon', 'posv'), |
| (a1, b1)) |
| lu, x, info = posv(a1, b1, lower=lower, |
| overwrite_a=overwrite_a, |
| overwrite_b=overwrite_b) |
| _solve_check(n, info) |
| rcond, info = pocon(lu, anorm) |
|
|
| _solve_check(n, info, lamch, rcond) |
|
|
| if b_is_1D: |
| x = x.ravel() |
|
|
| return x |
|
|
|
|
| def solve_triangular(a, b, trans=0, lower=False, unit_diagonal=False, |
| overwrite_b=False, check_finite=True): |
| """ |
| Solve the equation `a x = b` for `x`, assuming a is a triangular matrix. |
| |
| Parameters |
| ---------- |
| a : (M, M) array_like |
| A triangular matrix |
| b : (M,) or (M, N) array_like |
| Right-hand side matrix in `a x = b` |
| lower : bool, optional |
| Use only data contained in the lower triangle of `a`. |
| Default is to use upper triangle. |
| trans : {0, 1, 2, 'N', 'T', 'C'}, optional |
| Type of system to solve: |
| |
| ======== ========= |
| trans system |
| ======== ========= |
| 0 or 'N' a x = b |
| 1 or 'T' a^T x = b |
| 2 or 'C' a^H x = b |
| ======== ========= |
| unit_diagonal : bool, optional |
| If True, diagonal elements of `a` are assumed to be 1 and |
| will not be referenced. |
| overwrite_b : bool, optional |
| Allow overwriting data in `b` (may enhance performance) |
| check_finite : bool, optional |
| Whether to check that the input matrices contain only finite numbers. |
| Disabling may give a performance gain, but may result in problems |
| (crashes, non-termination) if the inputs do contain infinities or NaNs. |
| |
| Returns |
| ------- |
| x : (M,) or (M, N) ndarray |
| Solution to the system `a x = b`. Shape of return matches `b`. |
| |
| Raises |
| ------ |
| LinAlgError |
| If `a` is singular |
| |
| Notes |
| ----- |
| .. versionadded:: 0.9.0 |
| |
| Examples |
| -------- |
| Solve the lower triangular system a x = b, where:: |
| |
| [3 0 0 0] [4] |
| a = [2 1 0 0] b = [2] |
| [1 0 1 0] [4] |
| [1 1 1 1] [2] |
| |
| >>> import numpy as np |
| >>> from scipy.linalg import solve_triangular |
| >>> a = np.array([[3, 0, 0, 0], [2, 1, 0, 0], [1, 0, 1, 0], [1, 1, 1, 1]]) |
| >>> b = np.array([4, 2, 4, 2]) |
| >>> x = solve_triangular(a, b, lower=True) |
| >>> x |
| array([ 1.33333333, -0.66666667, 2.66666667, -1.33333333]) |
| >>> a.dot(x) # Check the result |
| array([ 4., 2., 4., 2.]) |
| |
| """ |
|
|
| a1 = _asarray_validated(a, check_finite=check_finite) |
| b1 = _asarray_validated(b, check_finite=check_finite) |
| if len(a1.shape) != 2 or a1.shape[0] != a1.shape[1]: |
| raise ValueError('expected square matrix') |
| if a1.shape[0] != b1.shape[0]: |
| raise ValueError(f'shapes of a {a1.shape} and b {b1.shape} are incompatible') |
| overwrite_b = overwrite_b or _datacopied(b1, b) |
|
|
| trans = {'N': 0, 'T': 1, 'C': 2}.get(trans, trans) |
| trtrs, = get_lapack_funcs(('trtrs',), (a1, b1)) |
| if a1.flags.f_contiguous or trans == 2: |
| x, info = trtrs(a1, b1, overwrite_b=overwrite_b, lower=lower, |
| trans=trans, unitdiag=unit_diagonal) |
| else: |
| |
| x, info = trtrs(a1.T, b1, overwrite_b=overwrite_b, lower=not lower, |
| trans=not trans, unitdiag=unit_diagonal) |
|
|
| if info == 0: |
| return x |
| if info > 0: |
| raise LinAlgError("singular matrix: resolution failed at diagonal %d" % |
| (info-1)) |
| raise ValueError('illegal value in %dth argument of internal trtrs' % |
| (-info)) |
|
|
|
|
| def solve_banded(l_and_u, ab, b, overwrite_ab=False, overwrite_b=False, |
| check_finite=True): |
| """ |
| Solve the equation a x = b for x, assuming a is banded matrix. |
| |
| The matrix a is stored in `ab` using the matrix diagonal ordered form:: |
| |
| ab[u + i - j, j] == a[i,j] |
| |
| Example of `ab` (shape of a is (6,6), `u` =1, `l` =2):: |
| |
| * a01 a12 a23 a34 a45 |
| a00 a11 a22 a33 a44 a55 |
| a10 a21 a32 a43 a54 * |
| a20 a31 a42 a53 * * |
| |
| Parameters |
| ---------- |
| (l, u) : (integer, integer) |
| Number of non-zero lower and upper diagonals |
| ab : (`l` + `u` + 1, M) array_like |
| Banded matrix |
| b : (M,) or (M, K) array_like |
| Right-hand side |
| overwrite_ab : bool, optional |
| Discard data in `ab` (may enhance performance) |
| overwrite_b : bool, optional |
| Discard data in `b` (may enhance performance) |
| check_finite : bool, optional |
| Whether to check that the input matrices contain only finite numbers. |
| Disabling may give a performance gain, but may result in problems |
| (crashes, non-termination) if the inputs do contain infinities or NaNs. |
| |
| Returns |
| ------- |
| x : (M,) or (M, K) ndarray |
| The solution to the system a x = b. Returned shape depends on the |
| shape of `b`. |
| |
| Examples |
| -------- |
| Solve the banded system a x = b, where:: |
| |
| [5 2 -1 0 0] [0] |
| [1 4 2 -1 0] [1] |
| a = [0 1 3 2 -1] b = [2] |
| [0 0 1 2 2] [2] |
| [0 0 0 1 1] [3] |
| |
| There is one nonzero diagonal below the main diagonal (l = 1), and |
| two above (u = 2). The diagonal banded form of the matrix is:: |
| |
| [* * -1 -1 -1] |
| ab = [* 2 2 2 2] |
| [5 4 3 2 1] |
| [1 1 1 1 *] |
| |
| >>> import numpy as np |
| >>> from scipy.linalg import solve_banded |
| >>> ab = np.array([[0, 0, -1, -1, -1], |
| ... [0, 2, 2, 2, 2], |
| ... [5, 4, 3, 2, 1], |
| ... [1, 1, 1, 1, 0]]) |
| >>> b = np.array([0, 1, 2, 2, 3]) |
| >>> x = solve_banded((1, 2), ab, b) |
| >>> x |
| array([-2.37288136, 3.93220339, -4. , 4.3559322 , -1.3559322 ]) |
| |
| """ |
|
|
| a1 = _asarray_validated(ab, check_finite=check_finite, as_inexact=True) |
| b1 = _asarray_validated(b, check_finite=check_finite, as_inexact=True) |
| |
| if a1.shape[-1] != b1.shape[0]: |
| raise ValueError("shapes of ab and b are not compatible.") |
| (nlower, nupper) = l_and_u |
| if nlower + nupper + 1 != a1.shape[0]: |
| raise ValueError("invalid values for the number of lower and upper " |
| "diagonals: l+u+1 (%d) does not equal ab.shape[0] " |
| "(%d)" % (nlower + nupper + 1, ab.shape[0])) |
|
|
| overwrite_b = overwrite_b or _datacopied(b1, b) |
| if a1.shape[-1] == 1: |
| b2 = np.array(b1, copy=(not overwrite_b)) |
| b2 /= a1[1, 0] |
| return b2 |
| if nlower == nupper == 1: |
| overwrite_ab = overwrite_ab or _datacopied(a1, ab) |
| gtsv, = get_lapack_funcs(('gtsv',), (a1, b1)) |
| du = a1[0, 1:] |
| d = a1[1, :] |
| dl = a1[2, :-1] |
| du2, d, du, x, info = gtsv(dl, d, du, b1, overwrite_ab, overwrite_ab, |
| overwrite_ab, overwrite_b) |
| else: |
| gbsv, = get_lapack_funcs(('gbsv',), (a1, b1)) |
| a2 = np.zeros((2*nlower + nupper + 1, a1.shape[1]), dtype=gbsv.dtype) |
| a2[nlower:, :] = a1 |
| lu, piv, x, info = gbsv(nlower, nupper, a2, b1, overwrite_ab=True, |
| overwrite_b=overwrite_b) |
| if info == 0: |
| return x |
| if info > 0: |
| raise LinAlgError("singular matrix") |
| raise ValueError('illegal value in %d-th argument of internal ' |
| 'gbsv/gtsv' % -info) |
|
|
|
|
| def solveh_banded(ab, b, overwrite_ab=False, overwrite_b=False, lower=False, |
| check_finite=True): |
| """ |
| Solve equation a x = b. a is Hermitian positive-definite banded matrix. |
| |
| Uses Thomas' Algorithm, which is more efficient than standard LU |
| factorization, but should only be used for Hermitian positive-definite |
| matrices. |
| |
| The matrix ``a`` is stored in `ab` either in lower diagonal or upper |
| diagonal ordered form: |
| |
| ab[u + i - j, j] == a[i,j] (if upper form; i <= j) |
| ab[ i - j, j] == a[i,j] (if lower form; i >= j) |
| |
| Example of `ab` (shape of ``a`` is (6, 6), number of upper diagonals, |
| ``u`` =2):: |
| |
| upper form: |
| * * a02 a13 a24 a35 |
| * a01 a12 a23 a34 a45 |
| a00 a11 a22 a33 a44 a55 |
| |
| lower form: |
| a00 a11 a22 a33 a44 a55 |
| a10 a21 a32 a43 a54 * |
| a20 a31 a42 a53 * * |
| |
| Cells marked with * are not used. |
| |
| Parameters |
| ---------- |
| ab : (``u`` + 1, M) array_like |
| Banded matrix |
| b : (M,) or (M, K) array_like |
| Right-hand side |
| overwrite_ab : bool, optional |
| Discard data in `ab` (may enhance performance) |
| overwrite_b : bool, optional |
| Discard data in `b` (may enhance performance) |
| lower : bool, optional |
| Is the matrix in the lower form. (Default is upper form) |
| check_finite : bool, optional |
| Whether to check that the input matrices contain only finite numbers. |
| Disabling may give a performance gain, but may result in problems |
| (crashes, non-termination) if the inputs do contain infinities or NaNs. |
| |
| Returns |
| ------- |
| x : (M,) or (M, K) ndarray |
| The solution to the system ``a x = b``. Shape of return matches shape |
| of `b`. |
| |
| Notes |
| ----- |
| In the case of a non-positive definite matrix ``a``, the solver |
| `solve_banded` may be used. |
| |
| Examples |
| -------- |
| Solve the banded system ``A x = b``, where:: |
| |
| [ 4 2 -1 0 0 0] [1] |
| [ 2 5 2 -1 0 0] [2] |
| A = [-1 2 6 2 -1 0] b = [2] |
| [ 0 -1 2 7 2 -1] [3] |
| [ 0 0 -1 2 8 2] [3] |
| [ 0 0 0 -1 2 9] [3] |
| |
| >>> import numpy as np |
| >>> from scipy.linalg import solveh_banded |
| |
| ``ab`` contains the main diagonal and the nonzero diagonals below the |
| main diagonal. That is, we use the lower form: |
| |
| >>> ab = np.array([[ 4, 5, 6, 7, 8, 9], |
| ... [ 2, 2, 2, 2, 2, 0], |
| ... [-1, -1, -1, -1, 0, 0]]) |
| >>> b = np.array([1, 2, 2, 3, 3, 3]) |
| >>> x = solveh_banded(ab, b, lower=True) |
| >>> x |
| array([ 0.03431373, 0.45938375, 0.05602241, 0.47759104, 0.17577031, |
| 0.34733894]) |
| |
| |
| Solve the Hermitian banded system ``H x = b``, where:: |
| |
| [ 8 2-1j 0 0 ] [ 1 ] |
| H = [2+1j 5 1j 0 ] b = [1+1j] |
| [ 0 -1j 9 -2-1j] [1-2j] |
| [ 0 0 -2+1j 6 ] [ 0 ] |
| |
| In this example, we put the upper diagonals in the array ``hb``: |
| |
| >>> hb = np.array([[0, 2-1j, 1j, -2-1j], |
| ... [8, 5, 9, 6 ]]) |
| >>> b = np.array([1, 1+1j, 1-2j, 0]) |
| >>> x = solveh_banded(hb, b) |
| >>> x |
| array([ 0.07318536-0.02939412j, 0.11877624+0.17696461j, |
| 0.10077984-0.23035393j, -0.00479904-0.09358128j]) |
| |
| """ |
| a1 = _asarray_validated(ab, check_finite=check_finite) |
| b1 = _asarray_validated(b, check_finite=check_finite) |
| |
| if a1.shape[-1] != b1.shape[0]: |
| raise ValueError("shapes of ab and b are not compatible.") |
|
|
| overwrite_b = overwrite_b or _datacopied(b1, b) |
| overwrite_ab = overwrite_ab or _datacopied(a1, ab) |
|
|
| if a1.shape[0] == 2: |
| ptsv, = get_lapack_funcs(('ptsv',), (a1, b1)) |
| if lower: |
| d = a1[0, :].real |
| e = a1[1, :-1] |
| else: |
| d = a1[1, :].real |
| e = a1[0, 1:].conj() |
| d, du, x, info = ptsv(d, e, b1, overwrite_ab, overwrite_ab, |
| overwrite_b) |
| else: |
| pbsv, = get_lapack_funcs(('pbsv',), (a1, b1)) |
| c, x, info = pbsv(a1, b1, lower=lower, overwrite_ab=overwrite_ab, |
| overwrite_b=overwrite_b) |
| if info > 0: |
| raise LinAlgError("%dth leading minor not positive definite" % info) |
| if info < 0: |
| raise ValueError('illegal value in %dth argument of internal ' |
| 'pbsv' % -info) |
| return x |
|
|
|
|
| def solve_toeplitz(c_or_cr, b, check_finite=True): |
| """Solve a Toeplitz system using Levinson Recursion |
| |
| The Toeplitz matrix has constant diagonals, with c as its first column |
| and r as its first row. If r is not given, ``r == conjugate(c)`` is |
| assumed. |
| |
| Parameters |
| ---------- |
| c_or_cr : array_like or tuple of (array_like, array_like) |
| The vector ``c``, or a tuple of arrays (``c``, ``r``). Whatever the |
| actual shape of ``c``, it will be converted to a 1-D array. If not |
| supplied, ``r = conjugate(c)`` is assumed; in this case, if c[0] is |
| real, the Toeplitz matrix is Hermitian. r[0] is ignored; the first row |
| of the Toeplitz matrix is ``[c[0], r[1:]]``. Whatever the actual shape |
| of ``r``, it will be converted to a 1-D array. |
| b : (M,) or (M, K) array_like |
| Right-hand side in ``T x = b``. |
| check_finite : bool, optional |
| Whether to check that the input matrices contain only finite numbers. |
| Disabling may give a performance gain, but may result in problems |
| (result entirely NaNs) if the inputs do contain infinities or NaNs. |
| |
| Returns |
| ------- |
| x : (M,) or (M, K) ndarray |
| The solution to the system ``T x = b``. Shape of return matches shape |
| of `b`. |
| |
| See Also |
| -------- |
| toeplitz : Toeplitz matrix |
| |
| Notes |
| ----- |
| The solution is computed using Levinson-Durbin recursion, which is faster |
| than generic least-squares methods, but can be less numerically stable. |
| |
| Examples |
| -------- |
| Solve the Toeplitz system T x = b, where:: |
| |
| [ 1 -1 -2 -3] [1] |
| T = [ 3 1 -1 -2] b = [2] |
| [ 6 3 1 -1] [2] |
| [10 6 3 1] [5] |
| |
| To specify the Toeplitz matrix, only the first column and the first |
| row are needed. |
| |
| >>> import numpy as np |
| >>> c = np.array([1, 3, 6, 10]) # First column of T |
| >>> r = np.array([1, -1, -2, -3]) # First row of T |
| >>> b = np.array([1, 2, 2, 5]) |
| |
| >>> from scipy.linalg import solve_toeplitz, toeplitz |
| >>> x = solve_toeplitz((c, r), b) |
| >>> x |
| array([ 1.66666667, -1. , -2.66666667, 2.33333333]) |
| |
| Check the result by creating the full Toeplitz matrix and |
| multiplying it by `x`. We should get `b`. |
| |
| >>> T = toeplitz(c, r) |
| >>> T.dot(x) |
| array([ 1., 2., 2., 5.]) |
| |
| """ |
| |
| |
| |
|
|
| r, c, b, dtype, b_shape = _validate_args_for_toeplitz_ops( |
| c_or_cr, b, check_finite, keep_b_shape=True) |
|
|
| |
| |
| vals = np.concatenate((r[-1:0:-1], c)) |
| if b is None: |
| raise ValueError('illegal value, `b` is a required argument') |
|
|
| if b.ndim == 1: |
| x, _ = levinson(vals, np.ascontiguousarray(b)) |
| else: |
| x = np.column_stack([levinson(vals, np.ascontiguousarray(b[:, i]))[0] |
| for i in range(b.shape[1])]) |
| x = x.reshape(*b_shape) |
|
|
| return x |
|
|
|
|
| def _get_axis_len(aname, a, axis): |
| ax = axis |
| if ax < 0: |
| ax += a.ndim |
| if 0 <= ax < a.ndim: |
| return a.shape[ax] |
| raise ValueError(f"'{aname}axis' entry is out of bounds") |
|
|
|
|
| def solve_circulant(c, b, singular='raise', tol=None, |
| caxis=-1, baxis=0, outaxis=0): |
| """Solve C x = b for x, where C is a circulant matrix. |
| |
| `C` is the circulant matrix associated with the vector `c`. |
| |
| The system is solved by doing division in Fourier space. The |
| calculation is:: |
| |
| x = ifft(fft(b) / fft(c)) |
| |
| where `fft` and `ifft` are the fast Fourier transform and its inverse, |
| respectively. For a large vector `c`, this is *much* faster than |
| solving the system with the full circulant matrix. |
| |
| Parameters |
| ---------- |
| c : array_like |
| The coefficients of the circulant matrix. |
| b : array_like |
| Right-hand side matrix in ``a x = b``. |
| singular : str, optional |
| This argument controls how a near singular circulant matrix is |
| handled. If `singular` is "raise" and the circulant matrix is |
| near singular, a `LinAlgError` is raised. If `singular` is |
| "lstsq", the least squares solution is returned. Default is "raise". |
| tol : float, optional |
| If any eigenvalue of the circulant matrix has an absolute value |
| that is less than or equal to `tol`, the matrix is considered to be |
| near singular. If not given, `tol` is set to:: |
| |
| tol = abs_eigs.max() * abs_eigs.size * np.finfo(np.float64).eps |
| |
| where `abs_eigs` is the array of absolute values of the eigenvalues |
| of the circulant matrix. |
| caxis : int |
| When `c` has dimension greater than 1, it is viewed as a collection |
| of circulant vectors. In this case, `caxis` is the axis of `c` that |
| holds the vectors of circulant coefficients. |
| baxis : int |
| When `b` has dimension greater than 1, it is viewed as a collection |
| of vectors. In this case, `baxis` is the axis of `b` that holds the |
| right-hand side vectors. |
| outaxis : int |
| When `c` or `b` are multidimensional, the value returned by |
| `solve_circulant` is multidimensional. In this case, `outaxis` is |
| the axis of the result that holds the solution vectors. |
| |
| Returns |
| ------- |
| x : ndarray |
| Solution to the system ``C x = b``. |
| |
| Raises |
| ------ |
| LinAlgError |
| If the circulant matrix associated with `c` is near singular. |
| |
| See Also |
| -------- |
| circulant : circulant matrix |
| |
| Notes |
| ----- |
| For a 1-D vector `c` with length `m`, and an array `b` |
| with shape ``(m, ...)``, |
| |
| solve_circulant(c, b) |
| |
| returns the same result as |
| |
| solve(circulant(c), b) |
| |
| where `solve` and `circulant` are from `scipy.linalg`. |
| |
| .. versionadded:: 0.16.0 |
| |
| Examples |
| -------- |
| >>> import numpy as np |
| >>> from scipy.linalg import solve_circulant, solve, circulant, lstsq |
| |
| >>> c = np.array([2, 2, 4]) |
| >>> b = np.array([1, 2, 3]) |
| >>> solve_circulant(c, b) |
| array([ 0.75, -0.25, 0.25]) |
| |
| Compare that result to solving the system with `scipy.linalg.solve`: |
| |
| >>> solve(circulant(c), b) |
| array([ 0.75, -0.25, 0.25]) |
| |
| A singular example: |
| |
| >>> c = np.array([1, 1, 0, 0]) |
| >>> b = np.array([1, 2, 3, 4]) |
| |
| Calling ``solve_circulant(c, b)`` will raise a `LinAlgError`. For the |
| least square solution, use the option ``singular='lstsq'``: |
| |
| >>> solve_circulant(c, b, singular='lstsq') |
| array([ 0.25, 1.25, 2.25, 1.25]) |
| |
| Compare to `scipy.linalg.lstsq`: |
| |
| >>> x, resid, rnk, s = lstsq(circulant(c), b) |
| >>> x |
| array([ 0.25, 1.25, 2.25, 1.25]) |
| |
| A broadcasting example: |
| |
| Suppose we have the vectors of two circulant matrices stored in an array |
| with shape (2, 5), and three `b` vectors stored in an array with shape |
| (3, 5). For example, |
| |
| >>> c = np.array([[1.5, 2, 3, 0, 0], [1, 1, 4, 3, 2]]) |
| >>> b = np.arange(15).reshape(-1, 5) |
| |
| We want to solve all combinations of circulant matrices and `b` vectors, |
| with the result stored in an array with shape (2, 3, 5). When we |
| disregard the axes of `c` and `b` that hold the vectors of coefficients, |
| the shapes of the collections are (2,) and (3,), respectively, which are |
| not compatible for broadcasting. To have a broadcast result with shape |
| (2, 3), we add a trivial dimension to `c`: ``c[:, np.newaxis, :]`` has |
| shape (2, 1, 5). The last dimension holds the coefficients of the |
| circulant matrices, so when we call `solve_circulant`, we can use the |
| default ``caxis=-1``. The coefficients of the `b` vectors are in the last |
| dimension of the array `b`, so we use ``baxis=-1``. If we use the |
| default `outaxis`, the result will have shape (5, 2, 3), so we'll use |
| ``outaxis=-1`` to put the solution vectors in the last dimension. |
| |
| >>> x = solve_circulant(c[:, np.newaxis, :], b, baxis=-1, outaxis=-1) |
| >>> x.shape |
| (2, 3, 5) |
| >>> np.set_printoptions(precision=3) # For compact output of numbers. |
| >>> x |
| array([[[-0.118, 0.22 , 1.277, -0.142, 0.302], |
| [ 0.651, 0.989, 2.046, 0.627, 1.072], |
| [ 1.42 , 1.758, 2.816, 1.396, 1.841]], |
| [[ 0.401, 0.304, 0.694, -0.867, 0.377], |
| [ 0.856, 0.758, 1.149, -0.412, 0.831], |
| [ 1.31 , 1.213, 1.603, 0.042, 1.286]]]) |
| |
| Check by solving one pair of `c` and `b` vectors (cf. ``x[1, 1, :]``): |
| |
| >>> solve_circulant(c[1], b[1, :]) |
| array([ 0.856, 0.758, 1.149, -0.412, 0.831]) |
| |
| """ |
| c = np.atleast_1d(c) |
| nc = _get_axis_len("c", c, caxis) |
| b = np.atleast_1d(b) |
| nb = _get_axis_len("b", b, baxis) |
| if nc != nb: |
| raise ValueError(f'Shapes of c {c.shape} and b {b.shape} are incompatible') |
|
|
| fc = np.fft.fft(np.moveaxis(c, caxis, -1), axis=-1) |
| abs_fc = np.abs(fc) |
| if tol is None: |
| |
| tol = abs_fc.max(axis=-1) * nc * np.finfo(np.float64).eps |
| if tol.shape != (): |
| tol.shape = tol.shape + (1,) |
| else: |
| tol = np.atleast_1d(tol) |
|
|
| near_zeros = abs_fc <= tol |
| is_near_singular = np.any(near_zeros) |
| if is_near_singular: |
| if singular == 'raise': |
| raise LinAlgError("near singular circulant matrix.") |
| else: |
| |
| |
| fc[near_zeros] = 1 |
|
|
| fb = np.fft.fft(np.moveaxis(b, baxis, -1), axis=-1) |
|
|
| q = fb / fc |
|
|
| if is_near_singular: |
| |
| |
| |
| |
| |
| mask = np.ones_like(b, dtype=bool) & near_zeros |
| q[mask] = 0 |
|
|
| x = np.fft.ifft(q, axis=-1) |
| if not (np.iscomplexobj(c) or np.iscomplexobj(b)): |
| x = x.real |
| if outaxis != -1: |
| x = np.moveaxis(x, -1, outaxis) |
| return x |
|
|
|
|
| |
| def inv(a, overwrite_a=False, check_finite=True): |
| """ |
| Compute the inverse of a matrix. |
| |
| Parameters |
| ---------- |
| a : array_like |
| Square matrix to be inverted. |
| overwrite_a : bool, optional |
| Discard data in `a` (may improve performance). Default is False. |
| check_finite : bool, optional |
| Whether to check that the input matrix contains only finite numbers. |
| Disabling may give a performance gain, but may result in problems |
| (crashes, non-termination) if the inputs do contain infinities or NaNs. |
| |
| Returns |
| ------- |
| ainv : ndarray |
| Inverse of the matrix `a`. |
| |
| Raises |
| ------ |
| LinAlgError |
| If `a` is singular. |
| ValueError |
| If `a` is not square, or not 2D. |
| |
| Examples |
| -------- |
| >>> import numpy as np |
| >>> from scipy import linalg |
| >>> a = np.array([[1., 2.], [3., 4.]]) |
| >>> linalg.inv(a) |
| array([[-2. , 1. ], |
| [ 1.5, -0.5]]) |
| >>> np.dot(a, linalg.inv(a)) |
| array([[ 1., 0.], |
| [ 0., 1.]]) |
| |
| """ |
| a1 = _asarray_validated(a, check_finite=check_finite) |
| if len(a1.shape) != 2 or a1.shape[0] != a1.shape[1]: |
| raise ValueError('expected square matrix') |
| overwrite_a = overwrite_a or _datacopied(a1, a) |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| getrf, getri, getri_lwork = get_lapack_funcs(('getrf', 'getri', |
| 'getri_lwork'), |
| (a1,)) |
| lu, piv, info = getrf(a1, overwrite_a=overwrite_a) |
| if info == 0: |
| lwork = _compute_lwork(getri_lwork, a1.shape[0]) |
|
|
| |
| |
| |
| |
| |
| |
| lwork = int(1.01 * lwork) |
| inv_a, info = getri(lu, piv, lwork=lwork, overwrite_lu=1) |
| if info > 0: |
| raise LinAlgError("singular matrix") |
| if info < 0: |
| raise ValueError('illegal value in %d-th argument of internal ' |
| 'getrf|getri' % -info) |
| return inv_a |
|
|
|
|
| |
|
|
| def det(a, overwrite_a=False, check_finite=True): |
| """ |
| Compute the determinant of a matrix |
| |
| The determinant is a scalar that is a function of the associated square |
| matrix coefficients. The determinant value is zero for singular matrices. |
| |
| Parameters |
| ---------- |
| a : (..., M, M) array_like |
| Input array to compute determinants for. |
| overwrite_a : bool, optional |
| Allow overwriting data in a (may enhance performance). |
| check_finite : bool, optional |
| Whether to check that the input matrix contains only finite numbers. |
| Disabling may give a performance gain, but may result in problems |
| (crashes, non-termination) if the inputs do contain infinities or NaNs. |
| |
| Returns |
| ------- |
| det : (...) float or complex |
| Determinant of `a`. For stacked arrays, a scalar is returned for each |
| (m, m) slice in the last two dimensions of the input. For example, an |
| input of shape (p, q, m, m) will produce a result of shape (p, q). If |
| all dimensions are 1 a scalar is returned regardless of ndim. |
| |
| Notes |
| ----- |
| The determinant is computed by performing an LU factorization of the |
| input with LAPACK routine 'getrf', and then calculating the product of |
| diagonal entries of the U factor. |
| |
| Even the input array is single precision (float32 or complex64), the result |
| will be returned in double precision (float64 or complex128) to prevent |
| overflows. |
| |
| Examples |
| -------- |
| >>> import numpy as np |
| >>> from scipy import linalg |
| >>> a = np.array([[1,2,3], [4,5,6], [7,8,9]]) # A singular matrix |
| >>> linalg.det(a) |
| 0.0 |
| >>> b = np.array([[0,2,3], [4,5,6], [7,8,9]]) |
| >>> linalg.det(b) |
| 3.0 |
| >>> # An array with the shape (3, 2, 2, 2) |
| >>> c = np.array([[[[1., 2.], [3., 4.]], |
| ... [[5., 6.], [7., 8.]]], |
| ... [[[9., 10.], [11., 12.]], |
| ... [[13., 14.], [15., 16.]]], |
| ... [[[17., 18.], [19., 20.]], |
| ... [[21., 22.], [23., 24.]]]]) |
| >>> linalg.det(c) # The resulting shape is (3, 2) |
| array([[-2., -2.], |
| [-2., -2.], |
| [-2., -2.]]) |
| >>> linalg.det(c[0, 0]) # Confirm the (0, 0) slice, [[1, 2], [3, 4]] |
| -2.0 |
| """ |
| |
|
|
| |
| a1 = np.asarray_chkfinite(a) if check_finite else np.asarray(a) |
| if a1.ndim < 2: |
| raise ValueError('The input array must be at least two-dimensional.') |
| if a1.shape[-1] != a1.shape[-2]: |
| raise ValueError('Last 2 dimensions of the array must be square' |
| f' but received shape {a1.shape}.') |
|
|
| |
| if a1.dtype.char not in 'fdFD': |
| dtype_char = lapack_cast_dict[a1.dtype.char] |
| if not dtype_char: |
| raise TypeError(f'The dtype "{a1.dtype.name}" cannot be cast ' |
| 'to float(32, 64) or complex(64, 128).') |
|
|
| a1 = a1.astype(dtype_char[0]) |
| overwrite_a = True |
|
|
| |
| if min(*a1.shape) == 0: |
| if a1.ndim == 2: |
| return np.float64(1.) |
| else: |
| return np.ones(shape=a1.shape[:-2], dtype=np.float64) |
|
|
| |
| if a1.shape[-2:] == (1, 1): |
| |
| if max(*a1.shape) > 1: |
| temp = np.squeeze(a1) |
| if a1.dtype.char in 'dD': |
| return temp |
| else: |
| return (temp.astype('d') if a1.dtype.char == 'f' else |
| temp.astype('D')) |
| else: |
| return (np.float64(a1.item()) if a1.dtype.char in 'fd' else |
| np.complex128(a1.item())) |
|
|
| |
| if not _datacopied(a1, a): |
| if not overwrite_a: |
| |
| a1 = a1.copy(order='C') |
| |
| |
|
|
| |
| |
| if not (a1.flags['C_CONTIGUOUS'] and a1.flags['WRITEABLE']): |
| a1 = a1.copy(order='C') |
|
|
| if a1.ndim == 2: |
| det = find_det_from_lu(a1) |
| |
| return (np.float64(det) if np.isrealobj(det) else np.complex128(det)) |
|
|
| |
| |
| dtype_char = a1.dtype.char |
| if dtype_char in 'fF': |
| dtype_char = 'd' if dtype_char.islower() else 'D' |
|
|
| det = np.empty(a1.shape[:-2], dtype=dtype_char) |
| for ind in product(*[range(x) for x in a1.shape[:-2]]): |
| det[ind] = find_det_from_lu(a1[ind]) |
| return det |
|
|
|
|
| |
| def lstsq(a, b, cond=None, overwrite_a=False, overwrite_b=False, |
| check_finite=True, lapack_driver=None): |
| """ |
| Compute least-squares solution to equation Ax = b. |
| |
| Compute a vector x such that the 2-norm ``|b - A x|`` is minimized. |
| |
| Parameters |
| ---------- |
| a : (M, N) array_like |
| Left-hand side array |
| b : (M,) or (M, K) array_like |
| Right hand side array |
| cond : float, optional |
| Cutoff for 'small' singular values; used to determine effective |
| rank of a. Singular values smaller than |
| ``cond * largest_singular_value`` are considered zero. |
| overwrite_a : bool, optional |
| Discard data in `a` (may enhance performance). Default is False. |
| overwrite_b : bool, optional |
| Discard data in `b` (may enhance performance). Default is False. |
| check_finite : bool, optional |
| Whether to check that the input matrices contain only finite numbers. |
| Disabling may give a performance gain, but may result in problems |
| (crashes, non-termination) if the inputs do contain infinities or NaNs. |
| lapack_driver : str, optional |
| Which LAPACK driver is used to solve the least-squares problem. |
| Options are ``'gelsd'``, ``'gelsy'``, ``'gelss'``. Default |
| (``'gelsd'``) is a good choice. However, ``'gelsy'`` can be slightly |
| faster on many problems. ``'gelss'`` was used historically. It is |
| generally slow but uses less memory. |
| |
| .. versionadded:: 0.17.0 |
| |
| Returns |
| ------- |
| x : (N,) or (N, K) ndarray |
| Least-squares solution. |
| residues : (K,) ndarray or float |
| Square of the 2-norm for each column in ``b - a x``, if ``M > N`` and |
| ``ndim(A) == n`` (returns a scalar if ``b`` is 1-D). Otherwise a |
| (0,)-shaped array is returned. |
| rank : int |
| Effective rank of `a`. |
| s : (min(M, N),) ndarray or None |
| Singular values of `a`. The condition number of ``a`` is |
| ``s[0] / s[-1]``. |
| |
| Raises |
| ------ |
| LinAlgError |
| If computation does not converge. |
| |
| ValueError |
| When parameters are not compatible. |
| |
| See Also |
| -------- |
| scipy.optimize.nnls : linear least squares with non-negativity constraint |
| |
| Notes |
| ----- |
| When ``'gelsy'`` is used as a driver, `residues` is set to a (0,)-shaped |
| array and `s` is always ``None``. |
| |
| Examples |
| -------- |
| >>> import numpy as np |
| >>> from scipy.linalg import lstsq |
| >>> import matplotlib.pyplot as plt |
| |
| Suppose we have the following data: |
| |
| >>> x = np.array([1, 2.5, 3.5, 4, 5, 7, 8.5]) |
| >>> y = np.array([0.3, 1.1, 1.5, 2.0, 3.2, 6.6, 8.6]) |
| |
| We want to fit a quadratic polynomial of the form ``y = a + b*x**2`` |
| to this data. We first form the "design matrix" M, with a constant |
| column of 1s and a column containing ``x**2``: |
| |
| >>> M = x[:, np.newaxis]**[0, 2] |
| >>> M |
| array([[ 1. , 1. ], |
| [ 1. , 6.25], |
| [ 1. , 12.25], |
| [ 1. , 16. ], |
| [ 1. , 25. ], |
| [ 1. , 49. ], |
| [ 1. , 72.25]]) |
| |
| We want to find the least-squares solution to ``M.dot(p) = y``, |
| where ``p`` is a vector with length 2 that holds the parameters |
| ``a`` and ``b``. |
| |
| >>> p, res, rnk, s = lstsq(M, y) |
| >>> p |
| array([ 0.20925829, 0.12013861]) |
| |
| Plot the data and the fitted curve. |
| |
| >>> plt.plot(x, y, 'o', label='data') |
| >>> xx = np.linspace(0, 9, 101) |
| >>> yy = p[0] + p[1]*xx**2 |
| >>> plt.plot(xx, yy, label='least squares fit, $y = a + bx^2$') |
| >>> plt.xlabel('x') |
| >>> plt.ylabel('y') |
| >>> plt.legend(framealpha=1, shadow=True) |
| >>> plt.grid(alpha=0.25) |
| >>> plt.show() |
| |
| """ |
| a1 = _asarray_validated(a, check_finite=check_finite) |
| b1 = _asarray_validated(b, check_finite=check_finite) |
| if len(a1.shape) != 2: |
| raise ValueError('Input array a should be 2D') |
| m, n = a1.shape |
| if len(b1.shape) == 2: |
| nrhs = b1.shape[1] |
| else: |
| nrhs = 1 |
| if m != b1.shape[0]: |
| raise ValueError('Shape mismatch: a and b should have the same number' |
| f' of rows ({m} != {b1.shape[0]}).') |
| if m == 0 or n == 0: |
| x = np.zeros((n,) + b1.shape[1:], dtype=np.common_type(a1, b1)) |
| if n == 0: |
| residues = np.linalg.norm(b1, axis=0)**2 |
| else: |
| residues = np.empty((0,)) |
| return x, residues, 0, np.empty((0,)) |
|
|
| driver = lapack_driver |
| if driver is None: |
| driver = lstsq.default_lapack_driver |
| if driver not in ('gelsd', 'gelsy', 'gelss'): |
| raise ValueError('LAPACK driver "%s" is not found' % driver) |
|
|
| lapack_func, lapack_lwork = get_lapack_funcs((driver, |
| '%s_lwork' % driver), |
| (a1, b1)) |
| real_data = True if (lapack_func.dtype.kind == 'f') else False |
|
|
| if m < n: |
| |
| |
| if len(b1.shape) == 2: |
| b2 = np.zeros((n, nrhs), dtype=lapack_func.dtype) |
| b2[:m, :] = b1 |
| else: |
| b2 = np.zeros(n, dtype=lapack_func.dtype) |
| b2[:m] = b1 |
| b1 = b2 |
|
|
| overwrite_a = overwrite_a or _datacopied(a1, a) |
| overwrite_b = overwrite_b or _datacopied(b1, b) |
|
|
| if cond is None: |
| cond = np.finfo(lapack_func.dtype).eps |
|
|
| if driver in ('gelss', 'gelsd'): |
| if driver == 'gelss': |
| lwork = _compute_lwork(lapack_lwork, m, n, nrhs, cond) |
| v, x, s, rank, work, info = lapack_func(a1, b1, cond, lwork, |
| overwrite_a=overwrite_a, |
| overwrite_b=overwrite_b) |
|
|
| elif driver == 'gelsd': |
| if real_data: |
| lwork, iwork = _compute_lwork(lapack_lwork, m, n, nrhs, cond) |
| x, s, rank, info = lapack_func(a1, b1, lwork, |
| iwork, cond, False, False) |
| else: |
| lwork, rwork, iwork = _compute_lwork(lapack_lwork, m, n, |
| nrhs, cond) |
| x, s, rank, info = lapack_func(a1, b1, lwork, rwork, iwork, |
| cond, False, False) |
| if info > 0: |
| raise LinAlgError("SVD did not converge in Linear Least Squares") |
| if info < 0: |
| raise ValueError('illegal value in %d-th argument of internal %s' |
| % (-info, lapack_driver)) |
| resids = np.asarray([], dtype=x.dtype) |
| if m > n: |
| x1 = x[:n] |
| if rank == n: |
| resids = np.sum(np.abs(x[n:])**2, axis=0) |
| x = x1 |
| return x, resids, rank, s |
|
|
| elif driver == 'gelsy': |
| lwork = _compute_lwork(lapack_lwork, m, n, nrhs, cond) |
| jptv = np.zeros((a1.shape[1], 1), dtype=np.int32) |
| v, x, j, rank, info = lapack_func(a1, b1, jptv, cond, |
| lwork, False, False) |
| if info < 0: |
| raise ValueError("illegal value in %d-th argument of internal " |
| "gelsy" % -info) |
| if m > n: |
| x1 = x[:n] |
| x = x1 |
| return x, np.array([], x.dtype), rank, None |
|
|
|
|
| lstsq.default_lapack_driver = 'gelsd' |
|
|
|
|
| @_deprecate_positional_args(version="1.14") |
| def pinv(a, *, atol=None, rtol=None, return_rank=False, check_finite=True, |
| cond=_NoValue, rcond=_NoValue): |
| """ |
| Compute the (Moore-Penrose) pseudo-inverse of a matrix. |
| |
| Calculate a generalized inverse of a matrix using its |
| singular-value decomposition ``U @ S @ V`` in the economy mode and picking |
| up only the columns/rows that are associated with significant singular |
| values. |
| |
| If ``s`` is the maximum singular value of ``a``, then the |
| significance cut-off value is determined by ``atol + rtol * s``. Any |
| singular value below this value is assumed insignificant. |
| |
| Parameters |
| ---------- |
| a : (M, N) array_like |
| Matrix to be pseudo-inverted. |
| atol : float, optional |
| Absolute threshold term, default value is 0. |
| |
| .. versionadded:: 1.7.0 |
| |
| rtol : float, optional |
| Relative threshold term, default value is ``max(M, N) * eps`` where |
| ``eps`` is the machine precision value of the datatype of ``a``. |
| |
| .. versionadded:: 1.7.0 |
| |
| return_rank : bool, optional |
| If True, return the effective rank of the matrix. |
| check_finite : bool, optional |
| Whether to check that the input matrix contains only finite numbers. |
| Disabling may give a performance gain, but may result in problems |
| (crashes, non-termination) if the inputs do contain infinities or NaNs. |
| cond, rcond : float, optional |
| In older versions, these values were meant to be used as ``atol`` with |
| ``rtol=0``. If both were given ``rcond`` overwrote ``cond`` and hence |
| the code was not correct. Thus using these are strongly discouraged and |
| the tolerances above are recommended instead. In fact, if provided, |
| atol, rtol takes precedence over these keywords. |
| |
| .. deprecated:: 1.7.0 |
| Deprecated in favor of ``rtol`` and ``atol`` parameters above and |
| will be removed in SciPy 1.14.0. |
| |
| .. versionchanged:: 1.3.0 |
| Previously the default cutoff value was just ``eps*f`` where ``f`` |
| was ``1e3`` for single precision and ``1e6`` for double precision. |
| |
| Returns |
| ------- |
| B : (N, M) ndarray |
| The pseudo-inverse of matrix `a`. |
| rank : int |
| The effective rank of the matrix. Returned if `return_rank` is True. |
| |
| Raises |
| ------ |
| LinAlgError |
| If SVD computation does not converge. |
| |
| See Also |
| -------- |
| pinvh : Moore-Penrose pseudoinverse of a hermitian matrix. |
| |
| Notes |
| ----- |
| If ``A`` is invertible then the Moore-Penrose pseudoinverse is exactly |
| the inverse of ``A`` [1]_. If ``A`` is not invertible then the |
| Moore-Penrose pseudoinverse computes the ``x`` solution to ``Ax = b`` such |
| that ``||Ax - b||`` is minimized [1]_. |
| |
| References |
| ---------- |
| .. [1] Penrose, R. (1956). On best approximate solutions of linear matrix |
| equations. Mathematical Proceedings of the Cambridge Philosophical |
| Society, 52(1), 17-19. doi:10.1017/S0305004100030929 |
| |
| Examples |
| -------- |
| |
| Given an ``m x n`` matrix ``A`` and an ``n x m`` matrix ``B`` the four |
| Moore-Penrose conditions are: |
| |
| 1. ``ABA = A`` (``B`` is a generalized inverse of ``A``), |
| 2. ``BAB = B`` (``A`` is a generalized inverse of ``B``), |
| 3. ``(AB)* = AB`` (``AB`` is hermitian), |
| 4. ``(BA)* = BA`` (``BA`` is hermitian) [1]_. |
| |
| Here, ``A*`` denotes the conjugate transpose. The Moore-Penrose |
| pseudoinverse is a unique ``B`` that satisfies all four of these |
| conditions and exists for any ``A``. Note that, unlike the standard |
| matrix inverse, ``A`` does not have to be a square matrix or have |
| linearly independent columns/rows. |
| |
| As an example, we can calculate the Moore-Penrose pseudoinverse of a |
| random non-square matrix and verify it satisfies the four conditions. |
| |
| >>> import numpy as np |
| >>> from scipy import linalg |
| >>> rng = np.random.default_rng() |
| >>> A = rng.standard_normal((9, 6)) |
| >>> B = linalg.pinv(A) |
| >>> np.allclose(A @ B @ A, A) # Condition 1 |
| True |
| >>> np.allclose(B @ A @ B, B) # Condition 2 |
| True |
| >>> np.allclose((A @ B).conj().T, A @ B) # Condition 3 |
| True |
| >>> np.allclose((B @ A).conj().T, B @ A) # Condition 4 |
| True |
| |
| """ |
| a = _asarray_validated(a, check_finite=check_finite) |
| u, s, vh = _decomp_svd.svd(a, full_matrices=False, check_finite=False) |
| t = u.dtype.char.lower() |
| maxS = np.max(s) |
|
|
| if rcond is not _NoValue or cond is not _NoValue: |
| warn('Use of the "cond" and "rcond" keywords are deprecated and ' |
| 'will be removed in SciPy 1.14.0. Use "atol" and ' |
| '"rtol" keywords instead', DeprecationWarning, stacklevel=2) |
|
|
| |
| if ((rcond not in (_NoValue, None) or cond not in (_NoValue, None)) |
| and (atol is None) and (rtol is None)): |
| atol = rcond if rcond not in (_NoValue, None) else cond |
| rtol = 0. |
|
|
| atol = 0. if atol is None else atol |
| rtol = max(a.shape) * np.finfo(t).eps if (rtol is None) else rtol |
|
|
| if (atol < 0.) or (rtol < 0.): |
| raise ValueError("atol and rtol values must be positive.") |
|
|
| val = atol + maxS * rtol |
| rank = np.sum(s > val) |
|
|
| u = u[:, :rank] |
| u /= s[:rank] |
| B = (u @ vh[:rank]).conj().T |
|
|
| if return_rank: |
| return B, rank |
| else: |
| return B |
|
|
|
|
| def pinvh(a, atol=None, rtol=None, lower=True, return_rank=False, |
| check_finite=True): |
| """ |
| Compute the (Moore-Penrose) pseudo-inverse of a Hermitian matrix. |
| |
| Calculate a generalized inverse of a complex Hermitian/real symmetric |
| matrix using its eigenvalue decomposition and including all eigenvalues |
| with 'large' absolute value. |
| |
| Parameters |
| ---------- |
| a : (N, N) array_like |
| Real symmetric or complex hermetian matrix to be pseudo-inverted |
| |
| atol : float, optional |
| Absolute threshold term, default value is 0. |
| |
| .. versionadded:: 1.7.0 |
| |
| rtol : float, optional |
| Relative threshold term, default value is ``N * eps`` where |
| ``eps`` is the machine precision value of the datatype of ``a``. |
| |
| .. versionadded:: 1.7.0 |
| |
| lower : bool, optional |
| Whether the pertinent array data is taken from the lower or upper |
| triangle of `a`. (Default: lower) |
| return_rank : bool, optional |
| If True, return the effective rank of the matrix. |
| check_finite : bool, optional |
| Whether to check that the input matrix contains only finite numbers. |
| Disabling may give a performance gain, but may result in problems |
| (crashes, non-termination) if the inputs do contain infinities or NaNs. |
| |
| Returns |
| ------- |
| B : (N, N) ndarray |
| The pseudo-inverse of matrix `a`. |
| rank : int |
| The effective rank of the matrix. Returned if `return_rank` is True. |
| |
| Raises |
| ------ |
| LinAlgError |
| If eigenvalue algorithm does not converge. |
| |
| See Also |
| -------- |
| pinv : Moore-Penrose pseudoinverse of a matrix. |
| |
| Examples |
| -------- |
| |
| For a more detailed example see `pinv`. |
| |
| >>> import numpy as np |
| >>> from scipy.linalg import pinvh |
| >>> rng = np.random.default_rng() |
| >>> a = rng.standard_normal((9, 6)) |
| >>> a = np.dot(a, a.T) |
| >>> B = pinvh(a) |
| >>> np.allclose(a, a @ B @ a) |
| True |
| >>> np.allclose(B, B @ a @ B) |
| True |
| |
| """ |
| a = _asarray_validated(a, check_finite=check_finite) |
| s, u = _decomp.eigh(a, lower=lower, check_finite=False) |
| t = u.dtype.char.lower() |
| maxS = np.max(np.abs(s)) |
|
|
| atol = 0. if atol is None else atol |
| rtol = max(a.shape) * np.finfo(t).eps if (rtol is None) else rtol |
|
|
| if (atol < 0.) or (rtol < 0.): |
| raise ValueError("atol and rtol values must be positive.") |
|
|
| val = atol + maxS * rtol |
| above_cutoff = (abs(s) > val) |
|
|
| psigma_diag = 1.0 / s[above_cutoff] |
| u = u[:, above_cutoff] |
|
|
| B = (u * psigma_diag) @ u.conj().T |
|
|
| if return_rank: |
| return B, len(psigma_diag) |
| else: |
| return B |
|
|
|
|
| def matrix_balance(A, permute=True, scale=True, separate=False, |
| overwrite_a=False): |
| """ |
| Compute a diagonal similarity transformation for row/column balancing. |
| |
| The balancing tries to equalize the row and column 1-norms by applying |
| a similarity transformation such that the magnitude variation of the |
| matrix entries is reflected to the scaling matrices. |
| |
| Moreover, if enabled, the matrix is first permuted to isolate the upper |
| triangular parts of the matrix and, again if scaling is also enabled, |
| only the remaining subblocks are subjected to scaling. |
| |
| The balanced matrix satisfies the following equality |
| |
| .. math:: |
| |
| B = T^{-1} A T |
| |
| The scaling coefficients are approximated to the nearest power of 2 |
| to avoid round-off errors. |
| |
| Parameters |
| ---------- |
| A : (n, n) array_like |
| Square data matrix for the balancing. |
| permute : bool, optional |
| The selector to define whether permutation of A is also performed |
| prior to scaling. |
| scale : bool, optional |
| The selector to turn on and off the scaling. If False, the matrix |
| will not be scaled. |
| separate : bool, optional |
| This switches from returning a full matrix of the transformation |
| to a tuple of two separate 1-D permutation and scaling arrays. |
| overwrite_a : bool, optional |
| This is passed to xGEBAL directly. Essentially, overwrites the result |
| to the data. It might increase the space efficiency. See LAPACK manual |
| for details. This is False by default. |
| |
| Returns |
| ------- |
| B : (n, n) ndarray |
| Balanced matrix |
| T : (n, n) ndarray |
| A possibly permuted diagonal matrix whose nonzero entries are |
| integer powers of 2 to avoid numerical truncation errors. |
| scale, perm : (n,) ndarray |
| If ``separate`` keyword is set to True then instead of the array |
| ``T`` above, the scaling and the permutation vectors are given |
| separately as a tuple without allocating the full array ``T``. |
| |
| Notes |
| ----- |
| This algorithm is particularly useful for eigenvalue and matrix |
| decompositions and in many cases it is already called by various |
| LAPACK routines. |
| |
| The algorithm is based on the well-known technique of [1]_ and has |
| been modified to account for special cases. See [2]_ for details |
| which have been implemented since LAPACK v3.5.0. Before this version |
| there are corner cases where balancing can actually worsen the |
| conditioning. See [3]_ for such examples. |
| |
| The code is a wrapper around LAPACK's xGEBAL routine family for matrix |
| balancing. |
| |
| .. versionadded:: 0.19.0 |
| |
| References |
| ---------- |
| .. [1] B.N. Parlett and C. Reinsch, "Balancing a Matrix for |
| Calculation of Eigenvalues and Eigenvectors", Numerische Mathematik, |
| Vol.13(4), 1969, :doi:`10.1007/BF02165404` |
| .. [2] R. James, J. Langou, B.R. Lowery, "On matrix balancing and |
| eigenvector computation", 2014, :arxiv:`1401.5766` |
| .. [3] D.S. Watkins. A case where balancing is harmful. |
| Electron. Trans. Numer. Anal, Vol.23, 2006. |
| |
| Examples |
| -------- |
| >>> import numpy as np |
| >>> from scipy import linalg |
| >>> x = np.array([[1,2,0], [9,1,0.01], [1,2,10*np.pi]]) |
| |
| >>> y, permscale = linalg.matrix_balance(x) |
| >>> np.abs(x).sum(axis=0) / np.abs(x).sum(axis=1) |
| array([ 3.66666667, 0.4995005 , 0.91312162]) |
| |
| >>> np.abs(y).sum(axis=0) / np.abs(y).sum(axis=1) |
| array([ 1.2 , 1.27041742, 0.92658316]) # may vary |
| |
| >>> permscale # only powers of 2 (0.5 == 2^(-1)) |
| array([[ 0.5, 0. , 0. ], # may vary |
| [ 0. , 1. , 0. ], |
| [ 0. , 0. , 1. ]]) |
| |
| """ |
|
|
| A = np.atleast_2d(_asarray_validated(A, check_finite=True)) |
|
|
| if not np.equal(*A.shape): |
| raise ValueError('The data matrix for balancing should be square.') |
|
|
| gebal = get_lapack_funcs(('gebal'), (A,)) |
| B, lo, hi, ps, info = gebal(A, scale=scale, permute=permute, |
| overwrite_a=overwrite_a) |
|
|
| if info < 0: |
| raise ValueError('xGEBAL exited with the internal error ' |
| f'"illegal value in argument number {-info}.". See ' |
| 'LAPACK documentation for the xGEBAL error codes.') |
|
|
| |
| scaling = np.ones_like(ps, dtype=float) |
| scaling[lo:hi+1] = ps[lo:hi+1] |
|
|
| |
| ps = ps.astype(int, copy=False) - 1 |
| n = A.shape[0] |
| perm = np.arange(n) |
|
|
| |
| if hi < n: |
| for ind, x in enumerate(ps[hi+1:][::-1], 1): |
| if n-ind == x: |
| continue |
| perm[[x, n-ind]] = perm[[n-ind, x]] |
|
|
| if lo > 0: |
| for ind, x in enumerate(ps[:lo]): |
| if ind == x: |
| continue |
| perm[[x, ind]] = perm[[ind, x]] |
|
|
| if separate: |
| return B, (scaling, perm) |
|
|
| |
| iperm = np.empty_like(perm) |
| iperm[perm] = np.arange(n) |
|
|
| return B, np.diag(scaling)[iperm, :] |
|
|
|
|
| def _validate_args_for_toeplitz_ops(c_or_cr, b, check_finite, keep_b_shape, |
| enforce_square=True): |
| """Validate arguments and format inputs for toeplitz functions |
| |
| Parameters |
| ---------- |
| c_or_cr : array_like or tuple of (array_like, array_like) |
| The vector ``c``, or a tuple of arrays (``c``, ``r``). Whatever the |
| actual shape of ``c``, it will be converted to a 1-D array. If not |
| supplied, ``r = conjugate(c)`` is assumed; in this case, if c[0] is |
| real, the Toeplitz matrix is Hermitian. r[0] is ignored; the first row |
| of the Toeplitz matrix is ``[c[0], r[1:]]``. Whatever the actual shape |
| of ``r``, it will be converted to a 1-D array. |
| b : (M,) or (M, K) array_like |
| Right-hand side in ``T x = b``. |
| check_finite : bool |
| Whether to check that the input matrices contain only finite numbers. |
| Disabling may give a performance gain, but may result in problems |
| (result entirely NaNs) if the inputs do contain infinities or NaNs. |
| keep_b_shape : bool |
| Whether to convert a (M,) dimensional b into a (M, 1) dimensional |
| matrix. |
| enforce_square : bool, optional |
| If True (default), this verifies that the Toeplitz matrix is square. |
| |
| Returns |
| ------- |
| r : array |
| 1d array corresponding to the first row of the Toeplitz matrix. |
| c: array |
| 1d array corresponding to the first column of the Toeplitz matrix. |
| b: array |
| (M,), (M, 1) or (M, K) dimensional array, post validation, |
| corresponding to ``b``. |
| dtype: numpy datatype |
| ``dtype`` stores the datatype of ``r``, ``c`` and ``b``. If any of |
| ``r``, ``c`` or ``b`` are complex, ``dtype`` is ``np.complex128``, |
| otherwise, it is ``np.float``. |
| b_shape: tuple |
| Shape of ``b`` after passing it through ``_asarray_validated``. |
| |
| """ |
|
|
| if isinstance(c_or_cr, tuple): |
| c, r = c_or_cr |
| c = _asarray_validated(c, check_finite=check_finite).ravel() |
| r = _asarray_validated(r, check_finite=check_finite).ravel() |
| else: |
| c = _asarray_validated(c_or_cr, check_finite=check_finite).ravel() |
| r = c.conjugate() |
|
|
| if b is None: |
| raise ValueError('`b` must be an array, not None.') |
|
|
| b = _asarray_validated(b, check_finite=check_finite) |
| b_shape = b.shape |
|
|
| is_not_square = r.shape[0] != c.shape[0] |
| if (enforce_square and is_not_square) or b.shape[0] != r.shape[0]: |
| raise ValueError('Incompatible dimensions.') |
|
|
| is_cmplx = np.iscomplexobj(r) or np.iscomplexobj(c) or np.iscomplexobj(b) |
| dtype = np.complex128 if is_cmplx else np.float64 |
| r, c, b = (np.asarray(i, dtype=dtype) for i in (r, c, b)) |
|
|
| if b.ndim == 1 and not keep_b_shape: |
| b = b.reshape(-1, 1) |
| elif b.ndim != 1: |
| b = b.reshape(b.shape[0], -1) |
|
|
| return r, c, b, dtype, b_shape |
|
|
|
|
| def matmul_toeplitz(c_or_cr, x, check_finite=False, workers=None): |
| """Efficient Toeplitz Matrix-Matrix Multiplication using FFT |
| |
| This function returns the matrix multiplication between a Toeplitz |
| matrix and a dense matrix. |
| |
| The Toeplitz matrix has constant diagonals, with c as its first column |
| and r as its first row. If r is not given, ``r == conjugate(c)`` is |
| assumed. |
| |
| Parameters |
| ---------- |
| c_or_cr : array_like or tuple of (array_like, array_like) |
| The vector ``c``, or a tuple of arrays (``c``, ``r``). Whatever the |
| actual shape of ``c``, it will be converted to a 1-D array. If not |
| supplied, ``r = conjugate(c)`` is assumed; in this case, if c[0] is |
| real, the Toeplitz matrix is Hermitian. r[0] is ignored; the first row |
| of the Toeplitz matrix is ``[c[0], r[1:]]``. Whatever the actual shape |
| of ``r``, it will be converted to a 1-D array. |
| x : (M,) or (M, K) array_like |
| Matrix with which to multiply. |
| check_finite : bool, optional |
| Whether to check that the input matrices contain only finite numbers. |
| Disabling may give a performance gain, but may result in problems |
| (result entirely NaNs) if the inputs do contain infinities or NaNs. |
| workers : int, optional |
| To pass to scipy.fft.fft and ifft. Maximum number of workers to use |
| for parallel computation. If negative, the value wraps around from |
| ``os.cpu_count()``. See scipy.fft.fft for more details. |
| |
| Returns |
| ------- |
| T @ x : (M,) or (M, K) ndarray |
| The result of the matrix multiplication ``T @ x``. Shape of return |
| matches shape of `x`. |
| |
| See Also |
| -------- |
| toeplitz : Toeplitz matrix |
| solve_toeplitz : Solve a Toeplitz system using Levinson Recursion |
| |
| Notes |
| ----- |
| The Toeplitz matrix is embedded in a circulant matrix and the FFT is used |
| to efficiently calculate the matrix-matrix product. |
| |
| Because the computation is based on the FFT, integer inputs will |
| result in floating point outputs. This is unlike NumPy's `matmul`, |
| which preserves the data type of the input. |
| |
| This is partly based on the implementation that can be found in [1]_, |
| licensed under the MIT license. More information about the method can be |
| found in reference [2]_. References [3]_ and [4]_ have more reference |
| implementations in Python. |
| |
| .. versionadded:: 1.6.0 |
| |
| References |
| ---------- |
| .. [1] Jacob R Gardner, Geoff Pleiss, David Bindel, Kilian |
| Q Weinberger, Andrew Gordon Wilson, "GPyTorch: Blackbox Matrix-Matrix |
| Gaussian Process Inference with GPU Acceleration" with contributions |
| from Max Balandat and Ruihan Wu. Available online: |
| https://github.com/cornellius-gp/gpytorch |
| |
| .. [2] J. Demmel, P. Koev, and X. Li, "A Brief Survey of Direct Linear |
| Solvers". In Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der |
| Vorst, editors. Templates for the Solution of Algebraic Eigenvalue |
| Problems: A Practical Guide. SIAM, Philadelphia, 2000. Available at: |
| http://www.netlib.org/utk/people/JackDongarra/etemplates/node384.html |
| |
| .. [3] R. Scheibler, E. Bezzam, I. Dokmanic, Pyroomacoustics: A Python |
| package for audio room simulations and array processing algorithms, |
| Proc. IEEE ICASSP, Calgary, CA, 2018. |
| https://github.com/LCAV/pyroomacoustics/blob/pypi-release/ |
| pyroomacoustics/adaptive/util.py |
| |
| .. [4] Marano S, Edwards B, Ferrari G and Fah D (2017), "Fitting |
| Earthquake Spectra: Colored Noise and Incomplete Data", Bulletin of |
| the Seismological Society of America., January, 2017. Vol. 107(1), |
| pp. 276-291. |
| |
| Examples |
| -------- |
| Multiply the Toeplitz matrix T with matrix x:: |
| |
| [ 1 -1 -2 -3] [1 10] |
| T = [ 3 1 -1 -2] x = [2 11] |
| [ 6 3 1 -1] [2 11] |
| [10 6 3 1] [5 19] |
| |
| To specify the Toeplitz matrix, only the first column and the first |
| row are needed. |
| |
| >>> import numpy as np |
| >>> c = np.array([1, 3, 6, 10]) # First column of T |
| >>> r = np.array([1, -1, -2, -3]) # First row of T |
| >>> x = np.array([[1, 10], [2, 11], [2, 11], [5, 19]]) |
| |
| >>> from scipy.linalg import toeplitz, matmul_toeplitz |
| >>> matmul_toeplitz((c, r), x) |
| array([[-20., -80.], |
| [ -7., -8.], |
| [ 9., 85.], |
| [ 33., 218.]]) |
| |
| Check the result by creating the full Toeplitz matrix and |
| multiplying it by ``x``. |
| |
| >>> toeplitz(c, r) @ x |
| array([[-20, -80], |
| [ -7, -8], |
| [ 9, 85], |
| [ 33, 218]]) |
| |
| The full matrix is never formed explicitly, so this routine |
| is suitable for very large Toeplitz matrices. |
| |
| >>> n = 1000000 |
| >>> matmul_toeplitz([1] + [0]*(n-1), np.ones(n)) |
| array([1., 1., 1., ..., 1., 1., 1.]) |
| |
| """ |
|
|
| from ..fft import fft, ifft, rfft, irfft |
|
|
| r, c, x, dtype, x_shape = _validate_args_for_toeplitz_ops( |
| c_or_cr, x, check_finite, keep_b_shape=False, enforce_square=False) |
| n, m = x.shape |
|
|
| T_nrows = len(c) |
| T_ncols = len(r) |
| p = T_nrows + T_ncols - 1 |
|
|
| embedded_col = np.concatenate((c, r[-1:0:-1])) |
|
|
| if np.iscomplexobj(embedded_col) or np.iscomplexobj(x): |
| fft_mat = fft(embedded_col, axis=0, workers=workers).reshape(-1, 1) |
| fft_x = fft(x, n=p, axis=0, workers=workers) |
|
|
| mat_times_x = ifft(fft_mat*fft_x, axis=0, |
| workers=workers)[:T_nrows, :] |
| else: |
| |
| fft_mat = rfft(embedded_col, axis=0, workers=workers).reshape(-1, 1) |
| fft_x = rfft(x, n=p, axis=0, workers=workers) |
|
|
| mat_times_x = irfft(fft_mat*fft_x, axis=0, |
| workers=workers, n=p)[:T_nrows, :] |
|
|
| return_shape = (T_nrows,) if len(x_shape) == 1 else (T_nrows, m) |
| return mat_times_x.reshape(*return_shape) |
|
|
