# Von Neumann Transform
[](https://github.com/xmiaocat/von-neumann-transform/actions/workflows/tests.yml)
[](https://github.com/xmiaocat/von-neumann-transform/actions/workflows/flake8.yml)
[](https://github.com/xmiaocat/von-neumann-transform/actions/workflows/mypy.yml)
[](https://codecov.io/gh/xmiaocat/von-neumann-transform)
A Python package for efficient computation of the von Neumann representation
of a signal given in the frequency domain.
The von Neumann representation is a joint time-frequency representation
defined in
- S. Fechner, F. Dimler, T. Brixner, G. Gerber, J. Tannor,
*Opt. Express* **2007**, *15*, 15387–15401.
- F. Dimler, S. Fechner, A. Rodenberg, T. Brixner, J. Tannor,
*New J. Phys.* **2009**, *11*, 105052.
## TODO
- [ ] Add consistency tests for solvers.
- [ ] Add consistency tests for inverse transform.
- [ ] Continuously integrate with GitHub Actions.
## Features
- Grid generation: Build uniform time-frequency grids in the
von Neumann plane.
- Signal projection: Compute the projection of the frequency-domain
signal onto the von Neumann basis functions *via*:
- Direct method: precompute and store the basis functions.
- Factorisation method: sequentially compute projections using
a factorisation of the basis.
- FFT-based method: compute the projection with the help of FFT.
- Overlap assembly & solvers: Solve for von Neumann coefficients
accounting for basis overlap using:
- Direct solve: assemble the overlap matrix and apply a
direct linear solver.
- Iterative solve: employ a matrix-vector operator and
iterative solver routines.
- Signal reconstruction: Reconstruct the original frequency-domain
signal from von Neumann coefficients.
- Type-safe API: Enums (`BasisMethod`, `MatVecMethod`, `SolverMethod`)
select algorithms, all functions and methods include type hints.
## Installation
Currently, this package is only available on GitHub.
```bash
git clone https://github.com/xmiaocat/von-neumann-transform
cd von-neumann-transform
pip install .
```
Alternatively, you can install in development mode with
```bash
pip install -e ".[dev]"
```
## Quickstart
```python
import numpy as np
from von_neumann_transform import VonNeumannTransform
NPOINTS = 4096 # length of the signal
W_MIN = 0.0 # minimum angular frequency
W_MAX = 5.0 # maximum angular frequency
# Your signal in the frequency domain
signal = np.random.rand(NPOINTS) + 1.0j * np.random.rand(NPOINTS)
# Create a Von Neumann Transform instance
vnt = VonNeumannTransform(NPOINTS, W_MIN, W_MAX)
# Compute the von Neumann representation of the signal
q_nm = vnt.transform(signal)
# Reconstruct the original signal from the von Neumann coefficients
signal_recon = vnt.inverse_transform(q_nm)
```
## Algorithmic Details
This section provides an overview of each method and its computational complexity.
Suppose the signal has length $N$. Then $k = \sqrt{N}$ is chosen, so the
von Neumann representation is a $k \times k$ matrix.
### Signal Projection
The signal projection is defined as
```math
\langle \alpha_{\omega_i t_j} | \epsilon \rangle
= \int_{-\infty}^{\infty} \alpha^*_{\omega_i t_j}(\omega) \epsilon(\omega) \mathrm{d}\omega
```
where $\alpha_{\omega_i t_j}(\omega)$ are the von Neumann basis functions
```math
\alpha_{\omega_n t_m}(\omega)
= \left(\frac{2\alpha}{\pi}\right)^{1/4}
\exp \left[ -\alpha (\omega - \omega_n)^2 - \mathrm{i} t_m (\omega - \omega_n) \right]
```
and $\epsilon(\omega)$ is the signal in the frequency domain.
In the discrete world, the basis functions $\alpha_{\omega_n t_m}(\omega)$
are sampled at $N$ points in the frequency domain, and therefore has the
shape `(k, k, N)`. The projection is then computed as
```math
\alpha_{nm} = \sum_{p=0}^{N-1} \alpha_{\omega_n t_m}(\omega_p) \epsilon(\omega_p)\,.
```
The time complexity of this operation is $\mathcal{O}(k^2 N)$.
The space complexity is also $\mathcal{O}(k^2 N)$ if the basis functions
are precomputed and stored.
The basis functions can be factorised as
```math
\begin{align}
\alpha_{\omega_n t_m}(\omega)
&= \left(\frac{2\alpha}{\pi}\right)^{1/4}
\exp \left[ -\alpha (\omega - \omega_n)^2 \right]
\exp \left[ -\mathrm{i} t_m \omega \right]
\exp \left[ \mathrm{i} t_m \omega_n \right] \\
&=: \left(\frac{2\alpha}{\pi}\right)^{1/4}
\alpha_{\omega_n}(\omega) \alpha_{t_m}(\omega) \alpha_{\omega_n t_m}\,.
\end{align}
```
The discretised version of the factors $\alpha_{\omega_n}(\omega)$,
$\alpha_{t_m}(\omega)$ and $\alpha_{\omega_n t_m}$ have the shapes
`(k, N)`, `(k, N)` and `(k, k)` respectively. This way,
although the time complexity of the projection is still
$\mathcal{O}(k^2 N)$, the space complexity can be reduced to
$\mathcal{O}(k N)$.
The factorisation shows another way to compute the projection.
Because of the factor $\exp \left[ \mathrm{i} t_m \omega_n \right]$,
this projection can be viewed as the (inverse) Fourier transform of the
signal $\epsilon(\omega)$ multiplied by the factor $\alpha_{\omega_n}(\omega)$
with a phase correction afterwards.
This reduces the time complexity to $\mathcal{O}(k N \log N)$.
The computational complexity of all three methods is summarised in the table below:
| Method | Time Complexity | Space Complexity |
|-----------------|-------------------|------------------|
| direct (`BasisMethod.DIRECT`) | $\mathcal{O}(k^2 N) = \mathcal{O}(N^2)$ | $\mathcal{O}(k^2 N) = \mathcal{O}(N^2)$ |
| factorisation (`BasisMethod.FACTORISE`) | $\mathcal{O}(k^2 N) = \mathcal{O}(N^2)$ | $\mathcal{O}(k N) = \mathcal{O}(N^{3/2})$ |
| FFT-based (`BasisMethod.FFT`) | $\mathcal{O}(k N \log N) = \mathcal{O}(N^{3/2} \log N)$ | $\mathcal{O}(k N) = \mathcal{O}(N^{3/2})$ |
### Overlap Assembly & Solvers
Since there are in total $k\times k = N$ basis functions, the overlap
matrix
```math
S_{(n,m),(i,j)} = \sqrt{\frac{2\alpha}{\pi}}
\exp \left[ -\frac{\alpha}{2}(\omega_n - \omega_i)^2
-\frac{1}{8\alpha}(t_j - t_m)^2
+\frac{\mathrm{i}}{2}(\omega_i - \omega_n)(t_j + t_m) \right]
```
has the dimension $N \times N$. Precomputing it and then solving the
linear system
```math
\sum_{(i,j)} S_{(n,m),(i,j)} q_{(i,j)} = \langle \alpha_{nm} | \epsilon \rangle
```
directly would have a time complexity of $\mathcal{O}(N^3)$
and a space complexity of $\mathcal{O}(N^2)$.
This can become quite expensive for signals with a large number of points,
In practice, the space is often the limiting factor. Therefore, the usual
approach would be to implement a matrix-vector operator
that computes the overlap-matrix-vector product on-the-fly
by contracting each row, then feeds that result into an iterative
solver like the conjugate gradient method to solve the linear system.
This approach has a time complexity of $\mathcal{O}(N^2)$ per iteration
and a space complexity of $\mathcal{O}(N)$, which is much more feasible
for large signals.
However, the repeated evaluation of the overlap matrix and
the matrix-vector product becomes very time-consuming.
This method is not implemented in this package.
Luckily, the overlap matrix has some structures that can be exploited.
This matrix is actually a **H**ermitian **P**ositive **D**efinite
**B**lock **T**oeplitz matrix with **T**oeplitz-**H**ankel
Hadamard Product **B**locks (HPDBTTHB).
The block Toeplitz structure means that we only need the first
block row and the first block column of the matrix to construct the
entire matrix. Because of the hermiticity, we even only need the
first block column of the dimension $N \times k$.
Even better, the block Toeplitz structure allows one to efficiently compute
the matrix-vector product by embedding the the matrix into a larger
$2N \times 2N$ block circulant matrix and then using batch FFTs to compute
the product in $\mathcal{O}(k^2 \log k)$ time.
This way, the expensive "ordinary" matrix-vector product only needs to be
computed on the much smaller blocks, thus reducing the time complexity
of the matrix-vector product to $\mathcal{O}(k^3)$.
Overall, the time complexity of this method is
$\mathcal{O}(k^3)$ and the space complexity is $\mathcal{O}(k^3)$.
In theory, the Toeplitz-Hankel Hadamard product structure of the blocks
can be exploited further to reduce the time complexity of the
matrix-vector product of blocks to $\mathcal{O}(k^2 \log k)$,
but this is not implemented in this package yet.
To accelerate the convergence, a circulant preconditioner is used
in the iterative solver, which does not increase the time complexity
for the iterative part but adds an additional $\mathcal{O}(k^4)$
overhead for the preparation of the preconditioner.
The computational complexity of the overlap assembly and solvers is summarised
in the table below:
| Method | Time Complexity | Space Complexity |
|-----------------|-------------------|------------------|
| direct (`MatVecMethod.DIRECT`) | $\mathcal{O}(N^3)$ | $\mathcal{O}(N^2)$ |
| rows of overlap + iterative solver (not implemented) | $\mathcal{O}(m\cdot N^2)$ | $\mathcal{O}(N)$ |
| Toeplitz + iterative solver + preconditioner (`MatVecMethod.TOEPLITZ_MATMUL` or `MatVecMethod.TOEPLITZ_EINSUM`) | $\mathcal{O}(N^2 + m\cdot N^{3/2})$ | $\mathcal{O}(N^{3/2})$ |
The variable $m$ is the number of iterations of the iterative solver.
### Signal Reconstruction
The signal reconstruction is simply the inverse of the signal projection,
and thus the same assortment of methods with the same computational
complexity applies.
## API Reference
### Class `VonNeumannTransform`
`VonNeumannTransform(npoints: int, omega_min: float, omega_max: float)`
Initialise a Von Neumann Transform instance.
- **Parameters:**
- `npoints`: Number of points in the frequency domain signal.
- `omega_min`: Minimum angular frequency.
- `omega_max`: Maximum angular frequency.
```
transform(
signal: np.ndarray,
basis_method: BasisMethod = BasisMethod.FFT,
matvec_method: MatVecMethod = MatVecMethod.TOEPLITZ_MATMUL,
solver_method: SolverMethod = SolverMethod.CG,
rtol: float = 1e-10,
atol: float = 0.0,
maxiter: int = 1000,
) -> np.ndarray
```
Computes the von Neumann representation of the signal.
- Parameters:
- signal (np.ndarray): Input signal in the frequency domain.
- basis_method (BasisMethod): Method to compute the projection
of the signal onto the basis functions.
Possible values are:
- `BasisMethod.DIRECT`: Directly compute the projection
by precomputing and storing the basis functions.
- `BasisMethod.FACTORISE`: Use the factorisation of the basis
functions to compute the projection.
- `BasisMethod.FFT`: Use the FFT to compute the projection.
- matvec_method (MatVecMethod): Method to compute the overlap matrix.
Possible values are:
- `MatVecMethod.DIRECT`: Directly assemble the overlap matrix.
Requires `SolverMethod.DIRECT`.
- `MatVecMethod.TOEPLITZ_MATMUL`: Use the Toeplitz structure
to compute the matrix-vector product.
- `MatVecMethod.TOEPLITZ_EINSUM`: Use the Toeplitz structure
to compute the matrix-vector product with einsum.
The latter two methods require an iterative solver
(`SolverMethod.CG`, `SolverMethod.BICGSTAB`, or `SolverMethod.LGMRES`).
- solver_method (SolverMethod): Method to solve the linear system.
- `SolverMethod.DIRECT`: Use a direct solver. Requires
`MatVecMethod.DIRECT`.
- `SolverMethod.CG`: Use the conjugate gradient method.
- `SolverMethod.BICGSTAB`: Use the biconjugate gradient
stabilised method.
- `SolverMethod.LGMRES`: Use the LGMRES method.
The iterative solvers require
`MatVecMethod.TOEPLITZ_MATMUL` or `MatVecMethod.TOEPLITZ_EINSUM`.
- rtol, atol (float): Relative and absolute tolerances for the
iterative solver.
- maxiter (int): Maximum number of iterations for the iterative
solver.
- Returns:
- q_nm (np.ndarray): Von Neumann coefficients, solution of the
linear system S * q_nm = alpha_nm.
```
inverse_transform(
q_nm: np.ndarray,
method: BasisMethod = BasisMethod.FFT,
) -> np.ndarray
```
Reconstructs the signal from the von Neumann coefficients.
- Parameters:
- q_nm (np.ndarray): Von Neumann coefficients.
- method (BasisMethod): Method to compute the inverse projection.
Possible values are:
- `BasisMethod.DIRECT`: Directly reconstruct the signal
by precomputing and storing the basis functions.
- `BasisMethod.FACTORISE`: Use the factorisation of the basis
functions to reconstruct the signal.
- `BasisMethod.FFT`: Use the FFT to reconstruct the signal.
- Returns:
- signal (np.ndarray): Reconstructed signal in the frequency domain.
### Enums
`BasisMethod`
Selects how basis functions are handled in the projection and reconstruction:
- `BasisMethod.DIRECT`: Precompute and store the basis functions.
- `BasisMethod.FACTORISE`: Use the factorisation of the basis functions.
- `BasisMethod.FFT`: Use the FFT to compute the projection and reconstruction.
`MatVecMethod`
Selects how the overlap operator is applied:
- `MatVecMethod.DIRECT`: Directly assemble the overlap matrix and multiply.
- `MatVecMethod.TOEPLITZ_MATMUL`: Use the Toeplitz structure to compute
the matrix-vector product.
- `MatVecMethod.TOEPLITZ_EINSUM`: Use the Toeplitz structure to compute
the matrix-vector product with einsum.
- `MatVecMethod.TOEPLITZ_HANKEL`: Use the Toeplitz-Hankel structure
to compute the matrix-vector product. **Not implemented yet.**
`SolverMethod`
Selects the linear solver for overlap inversion:
- `SolverMethod.DIRECT`: Use a direct solver.
- `SolverMethod.CG`: Use the conjugate gradient method.
- `SolverMethod.BICGSTAB`: Use the biconjugate gradient stabilised method.
- `SolverMethod.LGMRES`: Use the LGMRES method.
## License
Distributed under the Apache License 2.0.
See `LICENSE` for more information.
Raw data
{
"_id": null,
"home_page": null,
"name": "von-neumann-transform",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.11",
"maintainer_email": null,
"keywords": "joint time-frequency analysis, ultrashort laser pulse, von Neumann representation, von Neumann transform",
"author": null,
"author_email": "Xincheng Miao <xincheng.miao@uni-wuerzburg.de>",
"download_url": null,
"platform": null,
"description": "# Von Neumann Transform\n\n[](https://github.com/xmiaocat/von-neumann-transform/actions/workflows/tests.yml)\n[](https://github.com/xmiaocat/von-neumann-transform/actions/workflows/flake8.yml)\n[](https://github.com/xmiaocat/von-neumann-transform/actions/workflows/mypy.yml)\n[](https://codecov.io/gh/xmiaocat/von-neumann-transform)\n\nA Python package for efficient computation of the von Neumann representation \nof a signal given in the frequency domain.\nThe von Neumann representation is a joint time-frequency representation \ndefined in\n- S. Fechner, F. Dimler, T. Brixner, G. Gerber, J. Tannor,\n *Opt. Express* **2007**, *15*, 15387\u201315401.\n- F. Dimler, S. Fechner, A. Rodenberg, T. Brixner, J. Tannor,\n *New J. Phys.* **2009**, *11*, 105052.\n\n## TODO\n- [ ] Add consistency tests for solvers.\n- [ ] Add consistency tests for inverse transform.\n- [ ] Continuously integrate with GitHub Actions.\n\n## Features\n- Grid generation: Build uniform time-frequency grids in the\n von Neumann plane.\n- Signal projection: Compute the projection of the frequency-domain \n signal onto the von Neumann basis functions *via*:\n - Direct method: precompute and store the basis functions.\n - Factorisation method: sequentially compute projections using\n a factorisation of the basis.\n - FFT-based method: compute the projection with the help of FFT.\n- Overlap assembly & solvers: Solve for von Neumann coefficients\n accounting for basis overlap using:\n - Direct solve: assemble the overlap matrix and apply a\n direct linear solver.\n - Iterative solve: employ a matrix-vector operator and\n iterative solver routines.\n- Signal reconstruction: Reconstruct the original frequency-domain\n signal from von Neumann coefficients.\n- Type-safe API: Enums (`BasisMethod`, `MatVecMethod`, `SolverMethod`)\n select algorithms, all functions and methods include type hints.\n\n## Installation\nCurrently, this package is only available on GitHub.\n```bash\ngit clone https://github.com/xmiaocat/von-neumann-transform\ncd von-neumann-transform\npip install .\n```\nAlternatively, you can install in development mode with\n```bash\npip install -e \".[dev]\"\n```\n\n## Quickstart\n```python\nimport numpy as np\nfrom von_neumann_transform import VonNeumannTransform\n\nNPOINTS = 4096 # length of the signal\nW_MIN = 0.0 # minimum angular frequency\nW_MAX = 5.0 # maximum angular frequency\n\n# Your signal in the frequency domain\nsignal = np.random.rand(NPOINTS) + 1.0j * np.random.rand(NPOINTS)\n\n# Create a Von Neumann Transform instance\nvnt = VonNeumannTransform(NPOINTS, W_MIN, W_MAX)\n\n# Compute the von Neumann representation of the signal\nq_nm = vnt.transform(signal)\n\n# Reconstruct the original signal from the von Neumann coefficients\nsignal_recon = vnt.inverse_transform(q_nm)\n```\n\n## Algorithmic Details\nThis section provides an overview of each method and its computational complexity.\nSuppose the signal has length $N$. Then $k = \\sqrt{N}$ is chosen, so the\nvon Neumann representation is a $k \\times k$ matrix.\n\n### Signal Projection\nThe signal projection is defined as\n```math\n \\langle \\alpha_{\\omega_i t_j} | \\epsilon \\rangle\n = \\int_{-\\infty}^{\\infty} \\alpha^*_{\\omega_i t_j}(\\omega) \\epsilon(\\omega) \\mathrm{d}\\omega\n```\nwhere $\\alpha_{\\omega_i t_j}(\\omega)$ are the von Neumann basis functions\n```math\n \\alpha_{\\omega_n t_m}(\\omega) \n = \\left(\\frac{2\\alpha}{\\pi}\\right)^{1/4} \n \\exp \\left[ -\\alpha (\\omega - \\omega_n)^2 - \\mathrm{i} t_m (\\omega - \\omega_n) \\right]\n```\nand $\\epsilon(\\omega)$ is the signal in the frequency domain.\n\nIn the discrete world, the basis functions $\\alpha_{\\omega_n t_m}(\\omega)$\nare sampled at $N$ points in the frequency domain, and therefore has the\nshape `(k, k, N)`. The projection is then computed as\n```math\n \\alpha_{nm} = \\sum_{p=0}^{N-1} \\alpha_{\\omega_n t_m}(\\omega_p) \\epsilon(\\omega_p)\\,.\n```\nThe time complexity of this operation is $\\mathcal{O}(k^2 N)$.\nThe space complexity is also $\\mathcal{O}(k^2 N)$ if the basis functions\nare precomputed and stored. \n\nThe basis functions can be factorised as\n```math\n \\begin{align}\n \\alpha_{\\omega_n t_m}(\\omega) \n &= \\left(\\frac{2\\alpha}{\\pi}\\right)^{1/4} \n \\exp \\left[ -\\alpha (\\omega - \\omega_n)^2 \\right] \n \\exp \\left[ -\\mathrm{i} t_m \\omega \\right]\n \\exp \\left[ \\mathrm{i} t_m \\omega_n \\right] \\\\\n &=: \\left(\\frac{2\\alpha}{\\pi}\\right)^{1/4} \n \\alpha_{\\omega_n}(\\omega) \\alpha_{t_m}(\\omega) \\alpha_{\\omega_n t_m}\\,.\n \\end{align}\n```\nThe discretised version of the factors $\\alpha_{\\omega_n}(\\omega)$,\n$\\alpha_{t_m}(\\omega)$ and $\\alpha_{\\omega_n t_m}$ have the shapes\n`(k, N)`, `(k, N)` and `(k, k)` respectively. This way, \nalthough the time complexity of the projection is still\n$\\mathcal{O}(k^2 N)$, the space complexity can be reduced to\n$\\mathcal{O}(k N)$.\n\nThe factorisation shows another way to compute the projection.\nBecause of the factor $\\exp \\left[ \\mathrm{i} t_m \\omega_n \\right]$,\nthis projection can be viewed as the (inverse) Fourier transform of the\nsignal $\\epsilon(\\omega)$ multiplied by the factor $\\alpha_{\\omega_n}(\\omega)$\nwith a phase correction afterwards.\nThis reduces the time complexity to $\\mathcal{O}(k N \\log N)$.\n\nThe computational complexity of all three methods is summarised in the table below:\n| Method | Time Complexity | Space Complexity |\n|-----------------|-------------------|------------------|\n| direct (`BasisMethod.DIRECT`) | $\\mathcal{O}(k^2 N) = \\mathcal{O}(N^2)$ | $\\mathcal{O}(k^2 N) = \\mathcal{O}(N^2)$ |\n| factorisation (`BasisMethod.FACTORISE`) | $\\mathcal{O}(k^2 N) = \\mathcal{O}(N^2)$ | $\\mathcal{O}(k N) = \\mathcal{O}(N^{3/2})$ |\n| FFT-based (`BasisMethod.FFT`) | $\\mathcal{O}(k N \\log N) = \\mathcal{O}(N^{3/2} \\log N)$ | $\\mathcal{O}(k N) = \\mathcal{O}(N^{3/2})$ |\n\n### Overlap Assembly & Solvers\nSince there are in total $k\\times k = N$ basis functions, the overlap\nmatrix\n```math\n S_{(n,m),(i,j)} = \\sqrt{\\frac{2\\alpha}{\\pi}}\n \\exp \\left[ -\\frac{\\alpha}{2}(\\omega_n - \\omega_i)^2\n -\\frac{1}{8\\alpha}(t_j - t_m)^2 \n +\\frac{\\mathrm{i}}{2}(\\omega_i - \\omega_n)(t_j + t_m) \\right]\n```\nhas the dimension $N \\times N$. Precomputing it and then solving the\nlinear system\n```math\n \\sum_{(i,j)} S_{(n,m),(i,j)} q_{(i,j)} = \\langle \\alpha_{nm} | \\epsilon \\rangle\n```\ndirectly would have a time complexity of $\\mathcal{O}(N^3)$ \nand a space complexity of $\\mathcal{O}(N^2)$.\nThis can become quite expensive for signals with a large number of points,\n\nIn practice, the space is often the limiting factor. Therefore, the usual\napproach would be to implement a matrix-vector operator\nthat computes the overlap-matrix-vector product on-the-fly\nby contracting each row, then feeds that result into an iterative \nsolver like the conjugate gradient method to solve the linear system.\nThis approach has a time complexity of $\\mathcal{O}(N^2)$ per iteration\nand a space complexity of $\\mathcal{O}(N)$, which is much more feasible\nfor large signals.\nHowever, the repeated evaluation of the overlap matrix and\nthe matrix-vector product becomes very time-consuming.\nThis method is not implemented in this package.\n\nLuckily, the overlap matrix has some structures that can be exploited.\nThis matrix is actually a **H**ermitian **P**ositive **D**efinite \n**B**lock **T**oeplitz matrix with **T**oeplitz-**H**ankel\nHadamard Product **B**locks (HPDBTTHB).\nThe block Toeplitz structure means that we only need the first\nblock row and the first block column of the matrix to construct the\nentire matrix. Because of the hermiticity, we even only need the\nfirst block column of the dimension $N \\times k$.\nEven better, the block Toeplitz structure allows one to efficiently compute\nthe matrix-vector product by embedding the the matrix into a larger\n$2N \\times 2N$ block circulant matrix and then using batch FFTs to compute\nthe product in $\\mathcal{O}(k^2 \\log k)$ time.\nThis way, the expensive \"ordinary\" matrix-vector product only needs to be\ncomputed on the much smaller blocks, thus reducing the time complexity\nof the matrix-vector product to $\\mathcal{O}(k^3)$.\nOverall, the time complexity of this method is\n$\\mathcal{O}(k^3)$ and the space complexity is $\\mathcal{O}(k^3)$.\n\nIn theory, the Toeplitz-Hankel Hadamard product structure of the blocks\ncan be exploited further to reduce the time complexity of the \nmatrix-vector product of blocks to $\\mathcal{O}(k^2 \\log k)$,\nbut this is not implemented in this package yet.\n\nTo accelerate the convergence, a circulant preconditioner is used \nin the iterative solver, which does not increase the time complexity \nfor the iterative part but adds an additional $\\mathcal{O}(k^4)$ \noverhead for the preparation of the preconditioner.\n\nThe computational complexity of the overlap assembly and solvers is summarised \nin the table below:\n| Method | Time Complexity | Space Complexity |\n|-----------------|-------------------|------------------|\n| direct (`MatVecMethod.DIRECT`) | $\\mathcal{O}(N^3)$ | $\\mathcal{O}(N^2)$ |\n| rows of overlap + iterative solver (not implemented) | $\\mathcal{O}(m\\cdot N^2)$ | $\\mathcal{O}(N)$ |\n| Toeplitz + iterative solver + preconditioner (`MatVecMethod.TOEPLITZ_MATMUL` or `MatVecMethod.TOEPLITZ_EINSUM`) | $\\mathcal{O}(N^2 + m\\cdot N^{3/2})$ | $\\mathcal{O}(N^{3/2})$ |\n\nThe variable $m$ is the number of iterations of the iterative solver.\n\n### Signal Reconstruction\nThe signal reconstruction is simply the inverse of the signal projection,\nand thus the same assortment of methods with the same computational\ncomplexity applies.\n\n\n## API Reference\n\n### Class `VonNeumannTransform`\n\n`VonNeumannTransform(npoints: int, omega_min: float, omega_max: float)`\n\nInitialise a Von Neumann Transform instance.\n\n- **Parameters:**\n - `npoints`: Number of points in the frequency domain signal.\n - `omega_min`: Minimum angular frequency.\n - `omega_max`: Maximum angular frequency.\n\n```\ntransform(\n signal: np.ndarray,\n basis_method: BasisMethod = BasisMethod.FFT,\n matvec_method: MatVecMethod = MatVecMethod.TOEPLITZ_MATMUL,\n solver_method: SolverMethod = SolverMethod.CG,\n rtol: float = 1e-10,\n atol: float = 0.0,\n maxiter: int = 1000,\n) -> np.ndarray\n```\n\nComputes the von Neumann representation of the signal.\n\n- Parameters:\n - signal (np.ndarray): Input signal in the frequency domain.\n - basis_method (BasisMethod): Method to compute the projection\n of the signal onto the basis functions.\n Possible values are:\n - `BasisMethod.DIRECT`: Directly compute the projection\n by precomputing and storing the basis functions.\n - `BasisMethod.FACTORISE`: Use the factorisation of the basis\n functions to compute the projection.\n - `BasisMethod.FFT`: Use the FFT to compute the projection.\n - matvec_method (MatVecMethod): Method to compute the overlap matrix.\n Possible values are:\n - `MatVecMethod.DIRECT`: Directly assemble the overlap matrix.\n Requires `SolverMethod.DIRECT`.\n - `MatVecMethod.TOEPLITZ_MATMUL`: Use the Toeplitz structure\n to compute the matrix-vector product.\n - `MatVecMethod.TOEPLITZ_EINSUM`: Use the Toeplitz structure\n to compute the matrix-vector product with einsum.\n The latter two methods require an iterative solver\n (`SolverMethod.CG`, `SolverMethod.BICGSTAB`, or `SolverMethod.LGMRES`).\n - solver_method (SolverMethod): Method to solve the linear system.\n - `SolverMethod.DIRECT`: Use a direct solver. Requires\n `MatVecMethod.DIRECT`.\n - `SolverMethod.CG`: Use the conjugate gradient method.\n - `SolverMethod.BICGSTAB`: Use the biconjugate gradient\n stabilised method.\n - `SolverMethod.LGMRES`: Use the LGMRES method.\n The iterative solvers require\n `MatVecMethod.TOEPLITZ_MATMUL` or `MatVecMethod.TOEPLITZ_EINSUM`.\n - rtol, atol (float): Relative and absolute tolerances for the\n iterative solver.\n - maxiter (int): Maximum number of iterations for the iterative\n solver.\n\n- Returns:\n - q_nm (np.ndarray): Von Neumann coefficients, solution of the\n linear system S * q_nm = alpha_nm.\n\n```\ninverse_transform(\n q_nm: np.ndarray,\n method: BasisMethod = BasisMethod.FFT,\n) -> np.ndarray\n```\n\nReconstructs the signal from the von Neumann coefficients.\n\n- Parameters:\n - q_nm (np.ndarray): Von Neumann coefficients.\n - method (BasisMethod): Method to compute the inverse projection.\n Possible values are:\n - `BasisMethod.DIRECT`: Directly reconstruct the signal\n by precomputing and storing the basis functions.\n - `BasisMethod.FACTORISE`: Use the factorisation of the basis\n functions to reconstruct the signal.\n - `BasisMethod.FFT`: Use the FFT to reconstruct the signal.\n- Returns:\n - signal (np.ndarray): Reconstructed signal in the frequency domain.\n\n### Enums\n\n`BasisMethod`\nSelects how basis functions are handled in the projection and reconstruction:\n- `BasisMethod.DIRECT`: Precompute and store the basis functions.\n- `BasisMethod.FACTORISE`: Use the factorisation of the basis functions.\n- `BasisMethod.FFT`: Use the FFT to compute the projection and reconstruction.\n\n`MatVecMethod`\nSelects how the overlap operator is applied:\n- `MatVecMethod.DIRECT`: Directly assemble the overlap matrix and multiply.\n- `MatVecMethod.TOEPLITZ_MATMUL`: Use the Toeplitz structure to compute\n the matrix-vector product.\n- `MatVecMethod.TOEPLITZ_EINSUM`: Use the Toeplitz structure to compute\n the matrix-vector product with einsum.\n- `MatVecMethod.TOEPLITZ_HANKEL`: Use the Toeplitz-Hankel structure\n to compute the matrix-vector product. **Not implemented yet.**\n\n`SolverMethod`\nSelects the linear solver for overlap inversion:\n- `SolverMethod.DIRECT`: Use a direct solver.\n- `SolverMethod.CG`: Use the conjugate gradient method.\n- `SolverMethod.BICGSTAB`: Use the biconjugate gradient stabilised method.\n- `SolverMethod.LGMRES`: Use the LGMRES method.\n\n## License\nDistributed under the Apache License 2.0.\nSee `LICENSE` for more information.\n\n",
"bugtrack_url": null,
"license": null,
"summary": "A Python package for efficient von Neumann transform",
"version": "0.1.0",
"project_urls": {
"Homepage": "https://github.com/xmiaocat/von-neumann-transform",
"Issues": "https://github.com/xmiaocat/von-neumann-transform/issues"
},
"split_keywords": [
"joint time-frequency analysis",
" ultrashort laser pulse",
" von neumann representation",
" von neumann transform"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "ad55b6ed7e057bbfe08365d8a6adb23b3da89e88740fb37b527fd16bd608432d",
"md5": "9a20f2996eeb255422fbc0e3130d5e93",
"sha256": "817fef4d652318c1a0dc0a1dde7c74370d738af6343270033547e4009ec9dcc6"
},
"downloads": -1,
"filename": "von_neumann_transform-0.1.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "9a20f2996eeb255422fbc0e3130d5e93",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.11",
"size": 18675,
"upload_time": "2025-07-11T11:38:42",
"upload_time_iso_8601": "2025-07-11T11:38:42.289104Z",
"url": "https://files.pythonhosted.org/packages/ad/55/b6ed7e057bbfe08365d8a6adb23b3da89e88740fb37b527fd16bd608432d/von_neumann_transform-0.1.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2025-07-11 11:38:42",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "xmiaocat",
"github_project": "von-neumann-transform",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "von-neumann-transform"
}
JSON
