An official website of the United States government
This paper presents a scalable tensor-based approach to computing controllability and observability-type energy functions for nonlinear dynamical systems with polynomial drift and linear input and output maps. Using Kronecker product polynomial expansions, we convert the Hamilton- Jacobi-Bellman partial differential equations for the energy functions into a series of algebraic equations for the coefficients of the energy functions. We derive the specific tensor structure that arises from the Kronecker product representation and analyze the computational complexity to efficiently solve these equations. The convergence and scalability of the proposed energy function computation approach is demonstrated on a nonlinear reaction-diffusion model with cubic drift nonlinearity, for which we compute degree 3 energy function approximations in n = 1023 dimensions and degree 4 energy function approximations in n = 127 dimensions.
more »
« less
Computing Solutions to the Polynomial-Polynomial Regulator Problem*
We present a scalable approach to computing nonlinear balancing energy functions for control-affine systems with polynomial nonlinearities. Al’brekht’s powerseries method is used to solve the Hamilton–Jacobi– Bellman equations for polynomial approximations to the energy functions. The contribution of this article lies in the numerical implementation of the method based on the Kronecker product, enabling scalability to over 1000 state dimensions. The tensor structure and symmetries arising from the Kronecker product representation are key to the development of efficient and scalable algorithms.We derive the explicit algebraic structure for the equations, present rigorous theory for the solvability and algorithmic complexity of those equations, and provide general purpose open-source software implementations for the proposed algorithms. The method is illustrated on two simple academic models, followed by a high-dimensional semidiscretized PDE model of dimension as large as n = 1080.
more »
« less
- Award ID(s):
- 2130727
- PAR ID:
- 10657686
- Publisher / Repository:
- IEEE
- Date Published:
- Journal Name:
- Proceedings of the IEEE Conference on Decision Control
- ISSN:
- 2576-2370
- ISBN:
- 979-8-3503-1633-9
- Page Range / eLocation ID:
- 2689 to 2696
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We present a scalable tensor-based approach to computing input-normal/output-diagonal nonlinear balancing transformations for control-affine systems with polynomial nonlinearities. This transformation is necessary to determine the states that can be truncated when forming a reduced-order model. Given a polynomial representation for the controllability and observability energy functions, we derive the explicit equations to compute a polynomial transformation to induce input-normal/output-diagonal structure in the energy functions in the transformed coordinates. The transformation is computed degree-by-degree, similar to previous Taylor-series approaches in the literature. However, unlike previous works, we provide a detailed analysis of the transformation equations in Kronecker product form to enable a more scalable implementation. We derive the explicit algebraic structure for the equations, present rigorous analyses for the solvability and algorithmic complexity of those equations, and provide general purpose open-source software implementations for the proposed algorithms to stimulate broader use of nonlinear balanced truncation model reduction. We demonstrate that with our efficient implementation, computing the nonlinear transformation is approximately as expensive as computing the energy functions using state-of-the-art methods.more » « less
-
Hypergraphs and tensors extend classic graph and matrix theories to account for multiway relationships, which are ubiquitous in engineering, biological, and social systems. While the Kronecker product is a potent tool for analyzing the coupling of systems in a graph or matrix context, its utility in studying multiway interactions, such as those represented by tensors and hypergraphs, remains elusive. In this article, we present a comprehensive exploration of algebraic, structural, and spectral properties of the tensor Kronecker product. We express Tucker and tensor train decompositions and various tensor eigenvalues in terms of the tensor Kronecker product. Additionally, we utilize the tensor Kronecker product to form Kronecker hypergraphs, which are tensor-based hypergraph products, and investigate the structure and stability of polynomial dynamics on Kronecker hypergraphs. Finally, we provide numerical examples to demonstrate the utility of the tensor Kronecker product in computing Z-eigenvalues, performing various tensor decompositions, and determining the stability of polynomial systems.more » « less
-
Polynomial multiplication over the quotient ring is a critical operation in Ring Learning with Errors (Ring-LWE) based cryptosystems that are used for post-quantum cryptography and homomorphic encryption. This operation can be efficiently implemented using number-theoretic transform (NTT)-based architectures. Among these, pipelined parallel NTTbased polynomial multipliers are attractive for cloud computing as these are well suited for high throughput and low latency applications. For a given polynomial length, a pipelined parallel NTT-based multiplier can be designed with varying degrees of parallelism, resulting in different tradeoffs. Higher parallelism reduces latency but increases area and power consumption,and vice versa. In this paper, we develop a predictive model based on synthesized results for pipelined parallel NTT-based polynomial multipliers and analyze design tradeoffs in terms of area, power, energy, area-time product, and area-energy product across parallelism levels up to 128. We predict that, for very long polynomials, area and power differences between designs with varying levels of parallelism become negligible. In contrast, areatime product and energy per polynomial multiplication decrease with increased parallelism. Our findings suggest that, given area and power constraints, the highest feasible level of parallelism optimizes latency, area-time product, and energy per polynomial multiplication.more » « less
-
Polynomial multiplication is a key component in many post-quantum cryptography and homomorphic encryption schemes. One recurring variation, ternary polynomial multiplication over ring Zq/(xn+1) where one input polynomial has ternary coefficients {−1,0,1} and the other has large integer coefficients {0, q−1}, has recently drawn significant attention from various communities. Following this trend, this paper presents a novel SCALable and area-Efficient Systolic (SCALES) accelerator for ternary polynomial multiplication. In total, we have carried out three layers of coherent interdependent efforts. First, we have rigorously derived a novel block-processing strategy and algorithm based on the schoolbook method for polynomial multiplication. Then, we have innovatively implemented the proposed algorithm as the SCALES accelerator with the help of a number of field-programmable gate array (FPGA)-oriented optimization techniques. Lastly, we have conducted a thorough implementation analysis to showcase the efficiency of the proposed accelerator. The comparison demonstrated that the SCALES accelerator has at least 19.0% and 23.8% less equivalent area-time product (eATP) than the state-of-the-art designs. We hope this work can stimulate continued research in the field.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/CDC56724.2024.10885897
