Metadata-Version: 2.4
Name: hyhound
Version: 1.1.1
Summary: Hyperbolic Householder transformations for Up- and Downdating Cholesky factorizations.
Keywords: linear-algebra,cholesky,update,downdate,matrix
Author-Email: Pieter P <pieter.p.dev@outlook.com>
License-Expression: LGPL-3.0-or-later
License-File: LICENSE
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Science/Research
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Operating System :: POSIX :: Linux
Classifier: Operating System :: Microsoft :: Windows
Classifier: Operating System :: MacOS
Classifier: Typing :: Typed
Project-URL: Documentation, https://kul-optec.github.io/hyhound
Project-URL: Source, https://github.com/kul-optec/hyhound
Project-URL: Bug Tracker, https://github.com/kul-optec/hyhound/issues
Requires-Python: >=3.9
Requires-Dist: numpy<3
Provides-Extra: test
Requires-Dist: pytest<9,>=7.2.0; extra == "test"
Provides-Extra: docs
Requires-Dist: sphinx==8.2.3; extra == "docs"
Requires-Dist: sphinx-book-theme==1.1.4; extra == "docs"
Requires-Dist: numpydoc==1.9.0; extra == "docs"
Requires-Dist: breathe==4.36.0; extra == "docs"
Description-Content-Type: text/x-rst

.. image:: https://img.shields.io/badge/arXiv-Preprint-b31b1b
   :target: https://arxiv.org/abs/2503.15372v1
   :alt: arXiv Preprint

.. image:: https://github.com/kul-optec/hyhound/actions/workflows/linux.yml/badge.svg
   :target: https://github.com/kul-optec/hyhound/actions/workflows/linux.yml
   :alt: CI: Linux

.. image:: https://img.shields.io/pypi/dm/hyhound?label=PyPI&logo=python
   :target: https://pypi.org/project/hyhound
   :alt: PyPI Downloads


hyhound
=======

**Hy**\perbolic **Ho**\useholder transformations for **U**\p- ‘**n**’ **D**\owndating Cholesky factorizations.


Purpose
-------

Given a Cholesky factor :math:`L` of a dense matrix :math:`H`, the
``hyhound::update_cholesky`` function computes the Cholesky factor
:math:`\tilde L` of the matrix

.. math::

   \tilde H = \tilde L \tilde L^\top = H + A \Sigma A^\top,

where :math:`H,\tilde H\in\mathbb{R}^{n\times n}` with :math:`H \succ 0`
and :math:`\tilde H \succ 0`, :math:`A \in \mathbb{R}^{n\times m}`,
:math:`\Sigma \in \mathbb{R}^{m\times m}` diagonal,
and :math:`L, \tilde L\in\mathbb{R}^{n\times n}` lower triangular.

Computing :math:`\tilde L` in this way is done in
:math:`mn^2 + \mathcal{O}(n^2 + mn)` operations rather than the
:math:`\tfrac16 n^3 + \tfrac12 mn^2 + \mathcal{O}(n^2 + mn)` operations
required for the explicit evaluation and factorization of :math:`\tilde H`.
When :math:`m \ll n`, this results in a considerable speedup over full
factorization, enabling efficient low-rank updates of Cholesky
factorizations, for use in e.g. iterative algorithms for numerical
optimization.

Additionally, hyhound includes efficient routines for updating
factorizations of the Riccati recursion for optimal control problems.


Preprint
--------

The paper describing the algorithms in this repository can be found on arXiv:  
`https://arxiv.org/abs/2503.15372v1 <https://arxiv.org/abs/2503.15372v1>`_

.. code-block:: bibtex

   @misc{pas_blocked_2025,
      title = {Blocked {Cholesky} factorization updates of the {Riccati} recursion using hyperbolic {Householder} transformations},
      url = {http://arxiv.org/abs/2503.15372},
      doi = {10.48550/arXiv.2503.15372},
      publisher = {arXiv},
      author = {Pas, Pieter and Patrinos, Panagiotis},
      month = mar,
      year = {2025},
      note = {Accepted for publication in the Proceedings of CDC 2025}
   }
