imate.trace(method=’eigenvalue’)#

imate.trace(A, gram=False, p=1.0, return_info=False, method='eigenvalue', eigenvalues=None, assume_matrix='gen', non_zero_eig_fraction=0.9)

Trace of matrix using eigenvalue method.

See also

This page describes only the eigenvalue method. For other methods, see imate.trace().

Given the matrix \(\mathbf{A}\) and the real exponent \(p\), the following is computed:

\[\mathrm{trace} \left(\mathbf{A}^p \right).\]

If gram is True, then \(\mathbf{A}\) in the above is replaced by the Gramian matrix \(\mathbf{A}^{\intercal} \mathbf{A}\), and the following is instead computed:

\[\mathrm{trace} \left((\mathbf{A}^{\intercal}\mathbf{A})^p \right).\]

Parameters:

Anumpy.ndarray, scipy.sparse: A non-singular sparse or dense matrix. If gram is True, the matrix can be non-square.

Note

In the eigenvalue method, the matrix cannot be a type of Matrix or imate.AffineMatrixFunction classes.
grambool, default=False: If True, the trace of the Gramian matrix, \((\mathbf{A}^{\intercal}\mathbf{A})^p\), is computed. The Gramian matrix itself is not directly computed. If False, the trace of \(\mathbf{A}^p\) is computed.
pfloat, default=1.0: The real exponent \(p\) in \(\mathbf{A}^p\).
return_infobool, default=False: If True, this function also returns a dictionary containing information about the inner computation, such as process time, algorithm settings, etc.
eigenvaluesarray_like [float], default=None: The array of all eigenvalues of A, if available. The size of this array must be the same as the size of A. If None, the eigenvalues of A are computed.
assume_matrixstr {‘gen’, ‘sym’}, default: ‘gen’: Type of matrix. gen assumes generic matrix, while sym assumes A is symmetric.
non_zero_eig_fractionfloat, default=0.9: A fraction (between 0 and 1) of eigenvalues assumed to be non-zero. For large matrices, it is not possible to compute all eigenvalues, and only the largest eigenvalues can be computed and the rest are assumed to be negligible. By setting this parameter, a fraction of non-negligible eigenvalues is determined.

Returns:

tracefloat or numpy.array

Trace of matrix.

infodict

(Only if return_info is True) A dictionary of information with the following keys.

matrix:
- data_type: str, {float32, float64, float128}, type of the matrix data.
- gram: bool, whether the matrix A or its Gramian is considered.
- exponent: float, the exponent p in \(\mathbf{A}^p\).
- assume_matrix: str, {gen, sym}, determines whether matrix is generic or symmetric.
- size: (int, int), the size of matrix A.
- sparse: bool, whether the matrix A is sparse or dense.
- nnz: int, if A is sparse, the number of non-zero elements of A.
- density: float, if A is sparse, the density of A, which is the nnz divided by size squared.
- num_inquiries: int, for the eigenvalue method, this is always 1.
device:
- num_cpu_threads: int, number of CPU threads used in shared memory parallel processing.
- num_gpu_devices: int, for the eigenvalue method, this is always 0.
- num_gpu_multiprocessors: int, for the eigenvalue method, this is always 0.
- num_gpu_threads_per_multiprocessor: int, for eigenvalue method, this is always 0.
time:
- tot_wall_time: float, total elapsed time of computation.
- alg_wall_time: float, elapsed time of computation during only the algorithm execution.
- cpu_proc_time: float, the CPU processing time of computation.
solver:
- version: str, version of imate.
- method: ‘eigenvalue’

See also

imate.logdet
imate.traceinv
imate.schatten

Notes

Computational Complexity:

The eigenvalue method uses spectral decomposition. The computational complexity of this method is \(\mathcal{O}(n^3)\) where \(n\) is the matrix size. This method is only suitable for small matrices (\(n < 2^{12}\)). The solution is exact and can be used as a benchmark to test randomized methods of computing trace.

Warning

It is not recommended to use this method for sparse matrices, as not all eigenvalues of sparse matrices can be computed.

Examples

Dense matrix:

Compute the trace of \(\mathbf{A}^{2.5}\) for a symmetric Toeplitz matrix created by imate.toeplitz() function:

>>> # Import packages
>>> from imate import toeplitz, trace

>>> # Create a symmetric matrix (setting gram=True makes it symmetric)
>>> A = toeplitz(2, 1, size=100, gram=True)

>>> # Convert the sparse matrix to a dense matrix
>>> A = A.toarray()

>>> # Compute trace with eigenvalue method
>>> trace(A, p=2.5, method='eigenvalue', assume_matrix='sym')
8849.423700390627

Compute the trace of \((\mathbf{A}^{\intercal} \mathbf{A})^{2.5}\):

>>> # Compute trace with eigenvalue method
>>> trace(A, gram=True, p=2.5, method='eigenvalue',
...       assume_matrix='sym')
1533618.9999999988

Precomputed Eigenvalues:

Alternatively, compute the eigenvalues of A in advance, and pass it to this function:

>>> # Compute eigenvalues of symmetric matrix A.
>>> from scipy.linalg import eigh
>>> eigenvalues = eigh(A, eigvals_only=True)

>>> # Pass the eigenvalues to trace function
>>> trace(A, gram=True, p=2.5, method='eigenvalue',
...       eigenvalues=eigenvalues)
1533618.9999999988

Pre-computing eigenvalues can be useful if imate.trace() function should be called repeatedly for the same matrix A but other parameters may change, such as p.

Print Information:

Print information about the inner computation:

>>> tr, info = trace(A, method='eigenvalue', return_info=True)
>>> print(tr)
499.00000000000006

>>> # Print dictionary neatly using pprint
>>> from pprint import pprint
>>> pprint(info)
{
    'matrix': {
        'assume_matrix': 'gen',
        'data_type': b'float64',
        'density': 1.0,
        'exponent': 1.0,
        'gram': False,
        'nnz': 10000,
        'num_inquiries': 1,
        'size': (100, 100),
        'sparse': False
    },
    'solver': {
        'method': 'eigenvalue',
        'version': '0.15.0'
    },
    'device': {
        'num_cpu_threads': 8,
        'num_gpu_devices': 0,
        'num_gpu_multiprocessors': 0,
        'num_gpu_threads_per_multiprocessor': 0
    },
    'time': {
        'alg_wall_time': 0.00996067700907588,
        'cpu_proc_time': 0.01607515599999987,
        'tot_wall_time': 0.00996067700907588
    }
}

Sparse matrix:

Using a large matrix and ignoring 10% of its eigenvalues:

>>> # Generate a symmetric sparse matrix
>>> A = toeplitz(2, 1, size=2000, gram=True)

>>> # Assume only 80% of eigenvalues of A are non-zero
>>> trace(A, method='eigenvalue', assume_matrix='sym',
...       non_zero_eig_fraction=0.9)
9785.832766806298

The above result is only an approximation since not all eigenvalues of A are taken into account. To compare with the exact solution, use imate.sample_matrices.toeplitz_trace() function.

>>> from imate.sample_matrices import toeplitz_trace
>>> toeplitz_trace(2, 1, size=2000, gram=True)
9999

There is a significant difference between the approximation with 90% of eigenvalues and the actual solution. Because of this, it is not recommended to use the eigenvalue method to compute trace.