Internal algorithm modules
This page is for contributors implementing or modifying algorithm internals.
Public class-level API docs are in Algorithms.
Base contract
Use the base class contract when introducing a new algorithm module.
- class autolyap.algorithms.algorithm.Algorithm( )[source]
Bases:
ABCAbstract base class (ABC) for algorithms expressed in the state-space representation used by AutoLyap.
See 3. Algorithm representation for notation and representation conventions.
Note
For a given method, the state-space representation is not unique.
Concrete subclasses must implement
get_ABCD(); all other methods are implemented by this base class.
- __init__( ) None[source]
Initialize an
Algorithmwith the structural parameters of the representation.Parameters
n (
int): the state dimension, i.e., \(\bx^{k} \in \calH^{n}\).m (
int): the number of components \(m\) in the inclusion problem.m_bar_is (
List[int]): the list \((\bar{m}_i)_{i=1}^{m}\) of evaluation counts per component, with \(\bar{m}_i \in \mathbb{N}\) for each \(i\).I_func (
List[int]): the index set \(\IndexFunc\) for functional components.I_op (
List[int]): the index set \(\IndexOp\) for operator components.
Raises
ValueError: if \(n < 1\), \(m < 1\), \(m \neq \text{len}(m\_bar\_is)\), if any \(\bar{m}_i \le 0\), \(\IndexFunc\) and \(\IndexOp\) are not disjoint, do not cover \(\llbracket 1, m\rrbracket\), or are not strictly increasing sequences.
- _cache_get(
- cache: OrderedDict[Tuple[int, int], CacheValueT],
- key: Tuple[int, int],
Return one cached entry and refresh its LRU recency on hit.
keyis a horizon key(k_min, k_max). On a cache hit, the entry is moved to the end of thecollections.OrderedDictso it is treated as most recently used. On miss, returnNone.
- _cache_set(
- cache: OrderedDict[Tuple[int, int], CacheValueT],
- key: Tuple[int, int],
- value: CacheValueT,
Store one horizon-keyed cache entry with bounded LRU eviction.
The inserted/updated entry becomes most recently used. If the cache exceeds
_cache_maxsize, the least recently used entry is evicted. Returnsvalueso call sites can assign and return in one step.
- _clear_all_caches() None[source]
Clear every cached artifact after structural updates.
Structural fields (for example
n,m, and index partitions) may change matrix dimensions and projection maps. This clears dynamic horizon caches, static horizon caches (_cache_Us,_cache_Fs), and the projection cache_Ps_cache.
- _clear_dynamic_caches() None[source]
Clear caches tied to dynamic (non-structural) algorithm parameters.
These horizon-indexed caches are rebuilt when attributes such as step sizes change:
_cache_AsBsCsDs,_cache_Ys, and_cache_Xs.
- _compute_E(
- i: int,
- pairs: List[Tuple[int, int] | Tuple[str, str]],
- k_min: int,
- k_max: int,
- validate: bool = True,
Compute the lifted matrix \(E\) for one component and a list of pairs.
See 3. Algorithm representation for notation.
This method implements (5.17) from 5.1. Performance estimation via SDPs, using (5.8) together with (5.4)/ (5.5) and (5.6)/ (5.7) for non-star/star pairs, respectively. The resulting \(E\) is used in (5.12), (5.13), and (5.14) for the func-ineq, func-eq, and op cases, respectively, and therefore in (5.28) and (5.51) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.
The pair ordering in
pairsis preserved in the row stacking.Parameters
i (
int): component index \(i\).pairs (
List[Union[Tuple[int,int],Tuple[str,str]]]): list of \((j, k)\) pairs. For non-star pairs, \(j \in \llbracket 1,\bar{m}_i\rrbracket\) and \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\). For the star case, use (‘star’, ‘star’).k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).validate (
bool): Whether to validate inputs.
Returns
(
numpy.ndarray): The computed E matrix.
Raises
ValueError: if the pairs are malformed or the iteration bounds are invalid.
- _compute_F_aggregated(
- i: int,
- pairs: List[Tuple[int, int] | Tuple[str, str]],
- k_min: int,
- k_max: int,
- a: ndarray,
- validate: bool = True,
Compute one aggregated lifted vector \(F\).
See 3. Algorithm representation for notation.
This method implements (5.15) and (5.16) for the func-ineq and func-eq cases, respectively, from 5.1. Performance estimation via SDPs by stacking selected rows from
_get_Fs()and weighting them witha.The resulting vectors are the linear terms used in (5.28) and (5.51) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.
Parameters
i (
int): component index \(i\) (must satisfy \(i \in \IndexFunc\)).pairs (
List[Union[Tuple[int,int],Tuple[str,str]]]): list of \((j, k)\) pairs. For non-star pairs, \(j \in \llbracket 1,\bar{m}_i\rrbracket\) and \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\). For the star case, use (‘star’, ‘star’).k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).a (
numpy.ndarray): weight vector \(a \in \mathbb{R}^{\text{number of pairs}}\). This comes from the functional interpolation data (e.g., \(a_{(i,o)}^{\textup{func-ineq}}\) or \(a_{(i,o)}^{\textup{func-eq}}\)) forfunc-ineqandfunc-eqconstraints, respectively. See the functional interpolation-conditionget_data()contract or_get_component_data().validate (
bool): Whether to validate inputs.
Returns
(
numpy.ndarray): The aggregated F vector as a column vector.
Raises
ValueError: if any input conditions are not met.
- _compute_W(
- i: int,
- pairs: List[Tuple[int, int] | Tuple[str, str]],
- k_min: int,
- k_max: int,
- M: ndarray,
- validate: bool = True,
Compute one lifted quadratic constraint matrix \(W\).
See 3. Algorithm representation for notation.
This method implements the matrix definitions (5.12), (5.13), and (5.14) for the func-ineq, func-eq, and op cases, respectively, from 5.1. Performance estimation via SDPs using \(W = E^\top M E\).
The resulting matrices are the building blocks in (5.28) and (5.51) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.
Parameters
i (
int): component index \(i\).pairs (
List[Union[Tuple[int,int],Tuple[str,str]]]): list of \((j, k)\) pairs. For non-star pairs, \(j \in \llbracket 1,\bar{m}_i\rrbracket\) and \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\). For the star case, use (‘star’, ‘star’).k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).M (
numpy.ndarray): symmetric matrix \(M\) with shape \([2 \cdot (\text{number of pairs}) \times 2 \cdot (\text{number of pairs})]\). This comes from the interpolation data of the function/operator class (e.g., \(M_{(i,o)}^{\textup{func-ineq}}\), \(M_{(i,o)}^{\textup{func-eq}}\), or \(M_{(i,o)}^{\textup{op}}\)) forfunc-ineq,func-eq, andopconstraints, respectively. See the interpolation-conditionget_data()contract or_get_component_data().validate (
bool): Whether to validate inputs.
Returns
(
numpy.ndarray): The computed W matrix.
Raises
ValueError: if any input conditions are not met.
- _generate_F(
- i: int,
- j: int | None = None,
- k: int | None = None,
- star: bool = False,
- k_min: int = 0,
- k_max: int = 0,
Generate one lifted function-value selector row.
See 3. Algorithm representation for notation.
This method implements (5.9) from 5.1. Performance estimation via SDPs. Its outputs are combined into (5.15) and (5.16). These appear in both (5.28) and (5.51) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.
Parameters
i (
int): functional component index \(i\) (must satisfy \(i \in \IndexFunc\)).j (
Optional[int]): evaluation index \(j\) for the non-star case.k (
Optional[int]): iteration index \(k\) for the non-star case (must satisfy \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\)).star (
bool): if True, generate the star row.k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).
Returns
(
numpy.ndarray): A \(1 \times \text{total_dim}\) numpy array representing the generated F row.
Raises
ValueError: if the indices are invalid or inconsistent with the star/non-star case.
- _generate_U( ) ndarray[source]
Generate one lifted input matrix.
See 3. Algorithm representation for the state-space model (3.1).
This method implements (5.6) and (5.7) for the non-star and star cases, respectively, from 5.1. Performance estimation via SDPs. These matrices are then used in 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses respectively, through
_compute_E().Parameters
k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).k (
int): current iteration index \(k\) (required when star is False).star (
bool): if True, generate \(U_{\star}\).
Returns
(
numpy.ndarray): The generated matrix \(U_k^{k_{\textup{min}},k_{\textup{max}}}\) or \(U_{\star}^{k_{\textup{min}},k_{\textup{max}}}\) forstar=Falseandstar=True, respectively, each with\[n + (k_{\textup{max}} - k_{\textup{min}} + 1)\bar{m} + m\]columns.
Raises
ValueError: if k is missing when star is False or if \(k \notin \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\).
- _generate_X_k( ) ndarray[source]
Generate one lifted state matrix.
See 3. Algorithm representation for (3.1) and (3.2).
This method implements (5.3) in 5.1. Performance estimation via SDPs for
\[k \in \llbracket k_{\textup{min}}, k_{\textup{max}} + 1\rrbracket.\]The resulting matrices are used in (5.39), (5.43), and (5.58), i.e., in 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.
Parameters
sys_mats (
Dict[int,Tuple[numpy.ndarray,numpy.ndarray,numpy.ndarray,numpy.ndarray]]): dictionary mapping each iteration index \(k\) to \((A_k, B_k, C_k, D_k)\).k (
int): current iteration index \(k\).k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).
Returns
(
numpy.ndarray): The generated matrix \(X_k^{k_{\textup{min}},k_{\textup{max}}}\).
Raises
ValueError: if \(k \notin \llbracket k_{\textup{min}}, k_{\textup{max}}+1\rrbracket\).
- _generate_Y(
- sys_mats: Dict[int, Tuple[ndarray, ndarray, ndarray, ndarray]],
- k_min: int,
- k_max: int,
- k: int | None = None,
- star: bool = False,
Generate one lifted output matrix.
See 3. Algorithm representation for (3.1) and (3.2).
This method implements (5.4) and (5.5) for the non-star and star cases, respectively, from 5.1. Performance estimation via SDPs. These matrices are then used in 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses respectively, through
_compute_E().Parameters
sys_mats (
Dict[int,Tuple[numpy.ndarray,numpy.ndarray,numpy.ndarray,numpy.ndarray]]): dictionary mapping each iteration index \(k\) to \((A_k, B_k, C_k, D_k)\).k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).k (
int): current iteration index \(k\) (required when star is False).star (
bool): if True, generate \(Y_{\star}\).
Returns
(
numpy.ndarray): The generated matrix \(Y_k^{k_{\textup{min}},k_{\textup{max}}}\) or \(Y_{\star}^{k_{\textup{min}},k_{\textup{max}}}\) forstar=Falseandstar=True, respectively, each with\[n + (k_{\textup{max}} - k_{\textup{min}} + 1)\bar{m} + m\]columns.
Raises
ValueError: if k is missing when star is False.
- _get_AsBsCsDs( ) Dict[int, Tuple[ndarray, ndarray, ndarray, ndarray]][source]
Return a dictionary mapping each iteration index \(k\) to \((A_k, B_k, C_k, D_k)\) for \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\). In compact form:
\[\{(A_k, B_k, C_k, D_k)\}_{k=k_{\textup{min}}}^{k_{\textup{max}}}.\]Each entry is the tuple returned by
get_ABCD().These system matrices are used to build output and state matrices via
_get_Ys()and_get_Xs().Parameters
k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).
Returns
(
Dict[int,Tuple[numpy.ndarray,numpy.ndarray,numpy.ndarray,numpy.ndarray]]): A dictionary whose keys are iteration indices and values are tuples \((A_k, B_k, C_k, D_k)\), where\[A_k \in \mathbb{R}^{n \times n}, \quad B_k \in \mathbb{R}^{n \times \bar{m}}, \quad C_k \in \mathbb{R}^{\bar{m} \times n}, \quad D_k \in \mathbb{R}^{\bar{m} \times \bar{m}}.\]
Raises
ValueError: if \(k_{\textup{min}} < 0\) or \(k_{\textup{max}} < k_{\textup{min}}\).
- _get_Fs( ) Dict[Tuple[int, int | str, int | str], ndarray][source]
Return a dictionary of F matrices for all functional components. In compact form,
\[\{F_{(i,j,k)}^{k_{\textup{min}},k_{\textup{max}}}\}_{i\in\IndexFunc,\, j\in\llbracket 1,\bar{m}_i\rrbracket,\, k\in\llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket} \cup \{F_{(i,\star,\star)}^{k_{\textup{min}},k_{\textup{max}}}\}_{i\in\IndexFunc}.\]The dictionary keys are defined as follows. For non-star F matrices, keys are of the form \((i, j, k)\) with \(i \in \IndexFunc\), \(j \in \llbracket 1,\bar{m}_i\rrbracket\), and \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\). For star F matrices, keys are of the form \((i,\star,\star)\) for each \(i \in \IndexFunc\).
The matrix definition is (5.9) in 5.1. Performance estimation via SDPs. These F matrices are used by
_compute_F_aggregated()and enter the linear terms (5.15) and (5.16) that appear in (5.28) and (5.51) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.Parameters
k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).
Returns
(
Dict[Tuple[Any,Any,Any],numpy.ndarray]): A dictionary mapping keys to the corresponding F row matrices \(F_{(i,j,k)}^{k_{\textup{min}},k_{\textup{max}}}\) and \(F_{(i,\star,\star)}^{k_{\textup{min}},k_{\textup{max}}}\), where\[F_{(i,j,k)}^{k_{\textup{min}},k_{\textup{max}}}, F_{(i,\star,\star)}^{k_{\textup{min}},k_{\textup{max}}} \in \mathbb{R}^{1 \times d}, \quad d = (k_{\textup{max}} - k_{\textup{min}} + 1)\bar{m}_{\text{func}} + m_{\text{func}}.\]
Raises
ValueError: if \(k_{\textup{min}} < 0\) or \(k_{\textup{max}} < k_{\textup{min}}\).
- _get_Ps() Dict[Tuple[int, int | str], ndarray][source]
Return a dictionary of projection matrices \(P\). In compact form,
\[\{P_{(i,j)}\}_{j \in \llbracket 1,\NumEval_i\rrbracket,i \in \llbracket 1,m\rrbracket} \cup \{P_{(i,\star)}\}_{i \in \llbracket 1,m\rrbracket}.\]The matrix definitions are given by (5.8) in 5.1. Performance estimation via SDPs.
These projection matrices are used by
_compute_E()through (5.17), and therefore in (5.12), (5.13), and (5.14), which feed (5.28) and (5.51) in 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.Returns
(
Dict[Tuple[Any,Any],numpy.ndarray]): A dictionary whose keys are tuples \((i, j)\) with \(i \in \llbracket 1,m\rrbracket\), \(j \in \llbracket 1,\NumEval_i\rrbracket\), and \((i,\star)\), with values \(P_{(i,j)}\) and \(P_{(i,\star)}\), where\[P_{(i,j)} \in \mathbb{R}^{1 \times \NumEval}, \quad P_{(i,\star)} \in \mathbb{R}^{1 \times m}.\]
- _get_Us( ) Dict[int | str, ndarray][source]
Return a dictionary of U matrices for iterations \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\), including the star matrix. In compact form,
\[\{U_k^{k_{\textup{min}},k_{\textup{max}}}\}_{k=k_{\textup{min}}}^{k_{\textup{max}}} \cup \{U_{\star}^{k_{\textup{min}},k_{\textup{max}}}\}.\]The matrix definitions are (5.6) and (5.7) in 5.1. Performance estimation via SDPs. They are used in
_compute_E()(and therefore_compute_W()) through (5.17), and then in (5.12), (5.13), and (5.14), i.e., in lifted interpolation constraints that enter (5.28) and (5.51) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.Parameters
k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).
Returns
(
Dict[Any,numpy.ndarray]): A dictionary whose keys are iteration indices \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\) and ‘star’, with values \(U_k^{k_{\textup{min}},k_{\textup{max}}}\) and \(U_{\star}^{k_{\textup{min}},k_{\textup{max}}}\), respectively, where\[U_k^{k_{\textup{min}},k_{\textup{max}}} \in \mathbb{R}^{\bar{m} \times \left(n + (k_{\textup{max}} - k_{\textup{min}} + 1)\bar{m} + m\right)}, \quad U_{\star}^{k_{\textup{min}},k_{\textup{max}}} \in \mathbb{R}^{m \times \left(n + (k_{\textup{max}} - k_{\textup{min}} + 1)\bar{m} + m\right)}.\]
Raises
ValueError: if \(k_{\textup{min}} < 0\) or \(k_{\textup{max}} < k_{\textup{min}}\).
- _get_Xs( ) Dict[int, ndarray][source]
Return a dictionary mapping each iteration index \(k\) (for \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}} + 1\rrbracket\)) to the corresponding \(X_k\) matrix. In compact form,
\[\{X_k^{k_{\textup{min}},k_{\textup{max}}}\}_{k=k_{\textup{min}}}^{k_{\textup{max}}+1}.\]The matrix definition is (5.3) in 5.1. Performance estimation via SDPs.
The \(X_k\) matrices are constructed from system matrices returned by
_get_AsBsCsDs()(and thereforeget_ABCD()).In the convergence analyses, these matrices enter (5.39), (5.43), and (5.58) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.
Parameters
k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).
Returns
(
Dict[int,numpy.ndarray]): A dictionary mapping \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}+1\rrbracket\) to \(X_k^{k_{\textup{min}},k_{\textup{max}}}\), where\[X_k^{k_{\textup{min}},k_{\textup{max}}} \in \mathbb{R}^{n \times \left(n + (k_{\textup{max}} - k_{\textup{min}} + 1)\bar{m} + m\right)}.\]
Raises
ValueError: if \(k_{\textup{min}} < 0\) or \(k_{\textup{max}} < k_{\textup{min}}\).
- _get_Ys( ) Dict[int | str, ndarray][source]
Return a dictionary of Y matrices for iterations \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\), including \(Y_{\star}\). In compact form,
\[\{Y_k^{k_{\textup{min}},k_{\textup{max}}}\}_{k=k_{\textup{min}}}^{k_{\textup{max}}} \cup \{Y_{\star}^{k_{\textup{min}},k_{\textup{max}}}\}.\]The matrix definitions are (5.4) and (5.5) in 5.1. Performance estimation via SDPs. The \(Y\) matrices are constructed from system matrices returned by
_get_AsBsCsDs()(which callsget_ABCD()) and are used by_compute_E()through (5.17) for lifted interpolation constraints in (5.28) and (5.51) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.Parameters
k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).
Returns
(
Dict[Any,numpy.ndarray]): A dictionary whose keys are iteration indices \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\) and ‘star’, with values \(Y_k^{k_{\textup{min}},k_{\textup{max}}}\) and \(Y_{\star}^{k_{\textup{min}},k_{\textup{max}}}\), respectively, where\[Y_k^{k_{\textup{min}},k_{\textup{max}}} \in \mathbb{R}^{\bar{m} \times \left(n + (k_{\textup{max}} - k_{\textup{min}} + 1)\bar{m} + m\right)}, \quad Y_{\star}^{k_{\textup{min}},k_{\textup{max}}} \in \mathbb{R}^{m \times \left(n + (k_{\textup{max}} - k_{\textup{min}} + 1)\bar{m} + m\right)}.\]
Raises
ValueError: if \(k_{\textup{min}} < 0\) or \(k_{\textup{max}} < k_{\textup{min}}\).
- static _is_star_pair(
- j: object,
- k: object,
Return True when a pair corresponds to the star entry.
- _readonly_tuple( ) Tuple[ndarray, ndarray, ndarray, ndarray][source]
Return a tuple of read-only views for (A, B, C, D) matrices.
- static _readonly_view(
- array: ndarray,
Return a read-only view to discourage accidental mutation of cached matrices.
Parameters
array (
numpy.ndarray): Input array to view.
Returns
(
numpy.ndarray): A read-only view of the input array.
- _set_dynamic_parameter(
- name: str,
- value: object,
Update a dynamic scalar parameter only when its value changes.
This avoids unnecessary cache invalidation for repeated assignments of the same parameter value.
- static _validate_finite_real( ) float[source]
Validate a finite real scalar parameter.
- static _validate_nonstar_pair( ) Tuple[int, int][source]
Validate and normalize a non-star pair (j, k).
- static _validate_pairs_container( ) None[source]
Validate that pairs is a non-empty list/tuple of 2-tuples.
- classmethod _validate_positive_finite_real(
- value: object,
- name: str,
Validate a strictly positive finite real scalar parameter.
- abstractmethod get_ABCD(
- k: int,
See 3. Algorithm representation for notation and representation conventions.
Return the system matrices \((A_k, B_k, C_k, D_k)\) at iteration \(k\).
Parameters
k (
int): iteration index \(k\).
Returns
(
Tuple[numpy.ndarray,numpy.ndarray,numpy.ndarray,numpy.ndarray]): A tuple \((A_k, B_k, C_k, D_k)\) of numpy arrays with\[A_k \in \mathbb{R}^{n \times n}, \quad B_k \in \mathbb{R}^{n \times \bar{m}}, \quad C_k \in \mathbb{R}^{\bar{m} \times n}, \quad D_k \in \mathbb{R}^{\bar{m} \times \bar{m}}.\]
Private matrix/projection accessors
- Algorithm._get_AsBsCsDs( ) Dict[int, Tuple[ndarray, ndarray, ndarray, ndarray]][source]
Return a dictionary mapping each iteration index \(k\) to \((A_k, B_k, C_k, D_k)\) for \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\). In compact form:
\[\{(A_k, B_k, C_k, D_k)\}_{k=k_{\textup{min}}}^{k_{\textup{max}}}.\]Each entry is the tuple returned by
get_ABCD().These system matrices are used to build output and state matrices via
_get_Ys()and_get_Xs().Parameters
k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).
Returns
(
Dict[int,Tuple[numpy.ndarray,numpy.ndarray,numpy.ndarray,numpy.ndarray]]): A dictionary whose keys are iteration indices and values are tuples \((A_k, B_k, C_k, D_k)\), where\[A_k \in \mathbb{R}^{n \times n}, \quad B_k \in \mathbb{R}^{n \times \bar{m}}, \quad C_k \in \mathbb{R}^{\bar{m} \times n}, \quad D_k \in \mathbb{R}^{\bar{m} \times \bar{m}}.\]
Raises
ValueError: if \(k_{\textup{min}} < 0\) or \(k_{\textup{max}} < k_{\textup{min}}\).
- Algorithm._get_Us( ) Dict[int | str, ndarray][source]
Return a dictionary of U matrices for iterations \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\), including the star matrix. In compact form,
\[\{U_k^{k_{\textup{min}},k_{\textup{max}}}\}_{k=k_{\textup{min}}}^{k_{\textup{max}}} \cup \{U_{\star}^{k_{\textup{min}},k_{\textup{max}}}\}.\]The matrix definitions are (5.6) and (5.7) in 5.1. Performance estimation via SDPs. They are used in
_compute_E()(and therefore_compute_W()) through (5.17), and then in (5.12), (5.13), and (5.14), i.e., in lifted interpolation constraints that enter (5.28) and (5.51) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.Parameters
k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).
Returns
(
Dict[Any,numpy.ndarray]): A dictionary whose keys are iteration indices \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\) and ‘star’, with values \(U_k^{k_{\textup{min}},k_{\textup{max}}}\) and \(U_{\star}^{k_{\textup{min}},k_{\textup{max}}}\), respectively, where\[U_k^{k_{\textup{min}},k_{\textup{max}}} \in \mathbb{R}^{\bar{m} \times \left(n + (k_{\textup{max}} - k_{\textup{min}} + 1)\bar{m} + m\right)}, \quad U_{\star}^{k_{\textup{min}},k_{\textup{max}}} \in \mathbb{R}^{m \times \left(n + (k_{\textup{max}} - k_{\textup{min}} + 1)\bar{m} + m\right)}.\]
Raises
ValueError: if \(k_{\textup{min}} < 0\) or \(k_{\textup{max}} < k_{\textup{min}}\).
- Algorithm._get_Ys( ) Dict[int | str, ndarray][source]
Return a dictionary of Y matrices for iterations \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\), including \(Y_{\star}\). In compact form,
\[\{Y_k^{k_{\textup{min}},k_{\textup{max}}}\}_{k=k_{\textup{min}}}^{k_{\textup{max}}} \cup \{Y_{\star}^{k_{\textup{min}},k_{\textup{max}}}\}.\]The matrix definitions are (5.4) and (5.5) in 5.1. Performance estimation via SDPs. The \(Y\) matrices are constructed from system matrices returned by
_get_AsBsCsDs()(which callsget_ABCD()) and are used by_compute_E()through (5.17) for lifted interpolation constraints in (5.28) and (5.51) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.Parameters
k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).
Returns
(
Dict[Any,numpy.ndarray]): A dictionary whose keys are iteration indices \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\) and ‘star’, with values \(Y_k^{k_{\textup{min}},k_{\textup{max}}}\) and \(Y_{\star}^{k_{\textup{min}},k_{\textup{max}}}\), respectively, where\[Y_k^{k_{\textup{min}},k_{\textup{max}}} \in \mathbb{R}^{\bar{m} \times \left(n + (k_{\textup{max}} - k_{\textup{min}} + 1)\bar{m} + m\right)}, \quad Y_{\star}^{k_{\textup{min}},k_{\textup{max}}} \in \mathbb{R}^{m \times \left(n + (k_{\textup{max}} - k_{\textup{min}} + 1)\bar{m} + m\right)}.\]
Raises
ValueError: if \(k_{\textup{min}} < 0\) or \(k_{\textup{max}} < k_{\textup{min}}\).
- Algorithm._get_Xs( ) Dict[int, ndarray][source]
Return a dictionary mapping each iteration index \(k\) (for \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}} + 1\rrbracket\)) to the corresponding \(X_k\) matrix. In compact form,
\[\{X_k^{k_{\textup{min}},k_{\textup{max}}}\}_{k=k_{\textup{min}}}^{k_{\textup{max}}+1}.\]The matrix definition is (5.3) in 5.1. Performance estimation via SDPs.
The \(X_k\) matrices are constructed from system matrices returned by
_get_AsBsCsDs()(and thereforeget_ABCD()).In the convergence analyses, these matrices enter (5.39), (5.43), and (5.58) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.
Parameters
k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).
Returns
(
Dict[int,numpy.ndarray]): A dictionary mapping \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}+1\rrbracket\) to \(X_k^{k_{\textup{min}},k_{\textup{max}}}\), where\[X_k^{k_{\textup{min}},k_{\textup{max}}} \in \mathbb{R}^{n \times \left(n + (k_{\textup{max}} - k_{\textup{min}} + 1)\bar{m} + m\right)}.\]
Raises
ValueError: if \(k_{\textup{min}} < 0\) or \(k_{\textup{max}} < k_{\textup{min}}\).
- Algorithm._get_Ps() Dict[Tuple[int, int | str], ndarray][source]
Return a dictionary of projection matrices \(P\). In compact form,
\[\{P_{(i,j)}\}_{j \in \llbracket 1,\NumEval_i\rrbracket,i \in \llbracket 1,m\rrbracket} \cup \{P_{(i,\star)}\}_{i \in \llbracket 1,m\rrbracket}.\]The matrix definitions are given by (5.8) in 5.1. Performance estimation via SDPs.
These projection matrices are used by
_compute_E()through (5.17), and therefore in (5.12), (5.13), and (5.14), which feed (5.28) and (5.51) in 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.Returns
(
Dict[Tuple[Any,Any],numpy.ndarray]): A dictionary whose keys are tuples \((i, j)\) with \(i \in \llbracket 1,m\rrbracket\), \(j \in \llbracket 1,\NumEval_i\rrbracket\), and \((i,\star)\), with values \(P_{(i,j)}\) and \(P_{(i,\star)}\), where\[P_{(i,j)} \in \mathbb{R}^{1 \times \NumEval}, \quad P_{(i,\star)} \in \mathbb{R}^{1 \times m}.\]
- Algorithm._get_Fs( ) Dict[Tuple[int, int | str, int | str], ndarray][source]
Return a dictionary of F matrices for all functional components. In compact form,
\[\{F_{(i,j,k)}^{k_{\textup{min}},k_{\textup{max}}}\}_{i\in\IndexFunc,\, j\in\llbracket 1,\bar{m}_i\rrbracket,\, k\in\llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket} \cup \{F_{(i,\star,\star)}^{k_{\textup{min}},k_{\textup{max}}}\}_{i\in\IndexFunc}.\]The dictionary keys are defined as follows. For non-star F matrices, keys are of the form \((i, j, k)\) with \(i \in \IndexFunc\), \(j \in \llbracket 1,\bar{m}_i\rrbracket\), and \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\). For star F matrices, keys are of the form \((i,\star,\star)\) for each \(i \in \IndexFunc\).
The matrix definition is (5.9) in 5.1. Performance estimation via SDPs. These F matrices are used by
_compute_F_aggregated()and enter the linear terms (5.15) and (5.16) that appear in (5.28) and (5.51) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.Parameters
k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).
Returns
(
Dict[Tuple[Any,Any,Any],numpy.ndarray]): A dictionary mapping keys to the corresponding F row matrices \(F_{(i,j,k)}^{k_{\textup{min}},k_{\textup{max}}}\) and \(F_{(i,\star,\star)}^{k_{\textup{min}},k_{\textup{max}}}\), where\[F_{(i,j,k)}^{k_{\textup{min}},k_{\textup{max}}}, F_{(i,\star,\star)}^{k_{\textup{min}},k_{\textup{max}}} \in \mathbb{R}^{1 \times d}, \quad d = (k_{\textup{max}} - k_{\textup{min}} + 1)\bar{m}_{\text{func}} + m_{\text{func}}.\]
Raises
ValueError: if \(k_{\textup{min}} < 0\) or \(k_{\textup{max}} < k_{\textup{min}}\).
- Algorithm._compute_E(
- i: int,
- pairs: List[Tuple[int, int] | Tuple[str, str]],
- k_min: int,
- k_max: int,
- validate: bool = True,
Compute the lifted matrix \(E\) for one component and a list of pairs.
See 3. Algorithm representation for notation.
This method implements (5.17) from 5.1. Performance estimation via SDPs, using (5.8) together with (5.4)/ (5.5) and (5.6)/ (5.7) for non-star/star pairs, respectively. The resulting \(E\) is used in (5.12), (5.13), and (5.14) for the func-ineq, func-eq, and op cases, respectively, and therefore in (5.28) and (5.51) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.
The pair ordering in
pairsis preserved in the row stacking.Parameters
i (
int): component index \(i\).pairs (
List[Union[Tuple[int,int],Tuple[str,str]]]): list of \((j, k)\) pairs. For non-star pairs, \(j \in \llbracket 1,\bar{m}_i\rrbracket\) and \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\). For the star case, use (‘star’, ‘star’).k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).validate (
bool): Whether to validate inputs.
Returns
(
numpy.ndarray): The computed E matrix.
Raises
ValueError: if the pairs are malformed or the iteration bounds are invalid.
- Algorithm._compute_W(
- i: int,
- pairs: List[Tuple[int, int] | Tuple[str, str]],
- k_min: int,
- k_max: int,
- M: ndarray,
- validate: bool = True,
Compute one lifted quadratic constraint matrix \(W\).
See 3. Algorithm representation for notation.
This method implements the matrix definitions (5.12), (5.13), and (5.14) for the func-ineq, func-eq, and op cases, respectively, from 5.1. Performance estimation via SDPs using \(W = E^\top M E\).
The resulting matrices are the building blocks in (5.28) and (5.51) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.
Parameters
i (
int): component index \(i\).pairs (
List[Union[Tuple[int,int],Tuple[str,str]]]): list of \((j, k)\) pairs. For non-star pairs, \(j \in \llbracket 1,\bar{m}_i\rrbracket\) and \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\). For the star case, use (‘star’, ‘star’).k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).M (
numpy.ndarray): symmetric matrix \(M\) with shape \([2 \cdot (\text{number of pairs}) \times 2 \cdot (\text{number of pairs})]\). This comes from the interpolation data of the function/operator class (e.g., \(M_{(i,o)}^{\textup{func-ineq}}\), \(M_{(i,o)}^{\textup{func-eq}}\), or \(M_{(i,o)}^{\textup{op}}\)) forfunc-ineq,func-eq, andopconstraints, respectively. See the interpolation-conditionget_data()contract or_get_component_data().validate (
bool): Whether to validate inputs.
Returns
(
numpy.ndarray): The computed W matrix.
Raises
ValueError: if any input conditions are not met.
- Algorithm._compute_F_aggregated(
- i: int,
- pairs: List[Tuple[int, int] | Tuple[str, str]],
- k_min: int,
- k_max: int,
- a: ndarray,
- validate: bool = True,
Compute one aggregated lifted vector \(F\).
See 3. Algorithm representation for notation.
This method implements (5.15) and (5.16) for the func-ineq and func-eq cases, respectively, from 5.1. Performance estimation via SDPs by stacking selected rows from
_get_Fs()and weighting them witha.The resulting vectors are the linear terms used in (5.28) and (5.51) from 5.2. Iteration-independent analyses and 5.3. Iteration-dependent analyses, respectively.
Parameters
i (
int): component index \(i\) (must satisfy \(i \in \IndexFunc\)).pairs (
List[Union[Tuple[int,int],Tuple[str,str]]]): list of \((j, k)\) pairs. For non-star pairs, \(j \in \llbracket 1,\bar{m}_i\rrbracket\) and \(k \in \llbracket k_{\textup{min}}, k_{\textup{max}}\rrbracket\). For the star case, use (‘star’, ‘star’).k_min (
int): minimum iteration index \(k_{\textup{min}}\).k_max (
int): maximum iteration index \(k_{\textup{max}}\).a (
numpy.ndarray): weight vector \(a \in \mathbb{R}^{\text{number of pairs}}\). This comes from the functional interpolation data (e.g., \(a_{(i,o)}^{\textup{func-ineq}}\) or \(a_{(i,o)}^{\textup{func-eq}}\)) forfunc-ineqandfunc-eqconstraints, respectively. See the functional interpolation-conditionget_data()contract or_get_component_data().validate (
bool): Whether to validate inputs.
Returns
(
numpy.ndarray): The aggregated F vector as a column vector.
Raises
ValueError: if any input conditions are not met.
Module map
Class |
Implementation module |
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|