imate.trace(method=’exact’)#

imate.trace(A, gram=False, p=1.0, return_info=False, method='exact')

Trace of matrix using exact (direct) method.

See also

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

Given the matrix \(\mathbf{A}\) and the non-negative integer exponent \(p \geq 0\), 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 sparse or dense matrix. If gram is True, the matrix can be non-square.

Note

In the exact 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 non-negative integer 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.

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\).

    • 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 cholesky 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 cholesky method, this is always 0.

    • num_gpu_multiprocessors: int, for the cholesky method, this is always 0.

    • num_gpu_threads_per_multiprocessor: int, for the cholesky 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, CPU processing time of computation.

  • solver:

    • version: str, version of imate.

    • method: ‘exact’

See also

imate.logdet
imate.traceinv
imate.schatten

Notes

With the exact method, the trace is computed directly by summing up the diagonal elements of the matrix.

Computational Complexity:

  • If \(p=1\) and gram is False, the computational complexity is \(\mathcal{O}(n)\). methods.

  • If \(p=1\) and gram is True, the computational complexity is \(\mathcal{O}(n^2)\).

  • If \(p=2\) and gram is False, the computational complexity is \(\mathcal{O}(n^3)\).

  • If \(p=2\) and gram is True, the computational complexity is \(\mathcal{O}(n^3)\).

  • If \(p>2\), the computational complexity is \(\mathcal{O}(n^3)\).

Note

When \(p=1\) and gram is False, the exact method should always be used. If \(p \neq 1\), use the other methods.

Examples

Compute the trace of a sample sparse Toeplitz matrix created by imate.toeplitz() function.

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

>>> # Generate a sample matrix (a toeplitz matrix)
>>> A = toeplitz(2, 1, size=100)

>>> # Compute trace with the exact method (default method)
>>> trace(A)
200.0

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

>>> # Compute trace of the Gramian of A^3 using exact method
>>> trace(A, p=3, gram=True)
24307.0

Print information about the inner computation:

>>> tr, info = trace(A, return_info=True)
>>> print(tr)
200.0

>>> # Print dictionary neatly using pprint
>>> from pprint import pprint
>>> pprint(info)
{
    'matrix': {
        'data_type': b'float64',
        'density': 0.0199,
        'exponent': 1.0,
        'gram': False,
        'nnz': 199,
        'num_inquiries': 1,
        'size': (100, 100),
        'sparse': True
    },
    'solver': {
        'method': 'exact',
        'version': '0.14.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.00013329205103218555,
        'cpu_proc_time': 0.00017459900000016404,
        'tot_wall_time': 0.00013329205103218555
    }
}

Large matrix:

For large matrices, use the exact method only if \(p = 1\) and if gram is False.

>>> # Generate a matrix of size one million
>>> A = toeplitz(2, 1, size=1000000)

>>> # Approximate trace using stochastic Lanczos quadrature
>>> # with at least 100 Monte-Carlo sampling
>>> tr, info = trace(A, p=1, gram=False, return_info=True)
>>> print(tr)
2000000.0

>>> # Find the time it took to compute the above
>>> print(info['time'])
{
    'tot_wall_time': 0.004113928065635264,
    'alg_wall_time': 0.004113928065635264,
    'cpu_proc_time': 0.0041158319999681225
}