Search

We study a dynamic vector bin packing (DVBP) problem. We show hardness for shrinking arbitrary DVBP instances to size polynomial in the number of request types or in the maximal number of requests overlapping in time. We also present a simple polynomial-time data reduction algorithm that allows to recover $(1 + {\varepsilon})$-approximate solutions for arbitrary ${\varepsilon} > 0$. It shrinks instances from Microsoft Azure and Huawei Cloud by an order of magnitude for ${\varepsilon} = 0.02$., Comment: Version accepted to Operations Research Letters

We propose a Quantization Guided Training (QGT) method to guide DNN training towards optimized low-bit-precision targets and reach extreme compression levels below 8-bit precision. Unlike standard quantization-aware training (QAT) approaches, QGT uses customized regularization to encourage weight values towards a distribution that maximizes accuracy while reducing quantization errors. One of the main benefits of this approach is the ability to identify compression bottlenecks. We validate QGT using state-of-the-art model architectures on vision datasets. We also demonstrate the effectiveness of QGT with an 81KB tiny model for person detection down to 2-bit precision (representing 17.7x size reduction), while maintaining an accuracy drop of only 3% compared to a floating-point baseline., Comment: TinyML Summit, March 2021

Quantization for deep neural networks (DNN) have enabled developers to deploy models with less memory and more efficient low-power inference. However, not all DNN designs are friendly to quantization. For example, the popular Mobilenet architecture has been tuned to reduce parameter size and computational latency with separable depth-wise convolutions, but not all quantization algorithms work well and the accuracy can suffer against its float point versions. In this paper, we analyzed several root causes of quantization loss and proposed alternatives that do not rely on per-channel or training-aware approaches. We evaluate the image classification task on ImageNet dataset, and our post-training quantized 8-bit inference top-1 accuracy in within 0.7% of the floating point version., Comment: Embedded Vision Workshop, 16th European Conference on Computer Vision (ECCV), Aug 2020

Backus (1962) developed his technique for homogenization of a layered structure solely within the context of linear elastic theory. In this paper we propose an extended use of Backus average for finitely deformed materials of a layered structure. We attempt to use two different approaches to account for large deformations. The first approach utilizes the connections between linear and nonlinear transverse elasticity. For the second approach we use a formulation based on prestress in the material. We conclude that the first approach, although with some limitations, can be used successfully., Comment: 10 pages

We derive a general expression for the deformation-gradient tensor by invoking the standard definition of a gradient of a vector field in curvilinear coordinates. This expression shows the connection between the standard definition of a gradient of a vector field and the deformation gradient tensor in continuum mechanics. We illustrate its application in the context of problems discussed by Ogden [1997].

In this article we classify vessels producing solutions of some completely integrable PDEs, presenting a \textit{unified} approach for them. The classification includes such important examples as Korteweg-de Vries (KdV) and evolutionary Non Linear Schr\" odingier (ENLS) equations. In fact, employing basic matrix algebra techniques it is shown that there are exactly two canonical forms of such vessels, so that each canonical form generalize either KdV or ENLS equations. Particularly, Dirac canonical systems, whose evolution was recently inserted into the vessel theory, are shown to be equivalent to the ENLS equation in the sense of vessels. This work is important as a first step to classification of completely integrable PDEs, which are solvable by the theory of vessels. We note that a recent paper of the author, published in Journal of Mathematical Physics, showed that initial value problem with analytic initial potential for the KdV equation has at least a "narrowing" in time solution. The presented classification, inherits this idea and a similar theorem can be easily proved for the presented PDEs. Finally, the the resuts of the work serve as a basis for the investigation of the following problems: 1. hierarchy of the generalized KdV, ENLS equations (by generalizing the vessel equations), 2. new completely integrable PDEs (by changing the dimension of the outer space), 3. addressing the question of integrability of a given arbitrary PDE (the future classification will create a list of solvable by vessels equations, which may eventually include many existing classes of PDEs).

In this work we present an analogue of the inverse scattering for Canonical systems using theory of vessels and associated to them completely integrable systems. Analytic coefficients fits into this setting, significantly expanding the class of functions for which the inverse scattering exist. We also derive an evolutionary equation, arising from canonical systems, which describes the evolution of the logarithmic derivative of the tau function, associated to these systems, Comment: arXiv admin note: substantial text overlap with arXiv:1303.5324

We present a theory of Sturm-Liouville non-symmetric vessels, realizing an inverse scattering theory for the Sturm-Liouville operator with analytic potentials on the line. This construction is equivalent to the construction of a matrix spectral measure for the Sturm-Liouville operator, defined with an analytic potential on the line. Evolving such vessels we generate KdV vessels, realizing solutions of the KdV equation. As a consequence, we prove the following theorem: Suppose that q(x) is an analytic function on R. There exists a KdV vessel, which exists on a subset O of the plane. For each real x there exists positive T_x such that $\{x\}\times [-T_x,T_x]$ is in O. The potential q(x) is realized by the vessel for t=0. Since we also show that if q(x,t) is a solution of the KdV equation on a strip $R\times[0,T]$, then there exists a vessel, realizing it, the theory of vessels becomes a universal tool to study this problem. Finally, we notice that the idea of the proof applies to a similar existence of a solution for evolutionary NLS and Boussinesq equations, since both of these equations possess vessel constructions.

In this work we present a solution of the Boussinesq equation. The derived formulas include solitons, Schwartz class solutions and solutions, possessing singularities on a closed set Z of the (x,t) domain, obtained from the zeros of the tau function. The idea for solving the Boussinesq equation is identical to the (unified) idea of solving the KdV and the evolutionary NLS equations: we use a theory of evolutionary vessels. But a more powerful theory of non-symmetric evolutionary vessels is presented, inserting flexibility into the construction and allowing to deal with complex-valued solutions. A powerful scattering theory of Deift-Tomei-Trubowitz for a three dimensional operator, which is used to solve the Boussinesq equation, fits into our setting only in a particular case. On the other hand, we create a much wider class of solutions of the Boussinesq equation with singularities on a closed set $Z$.

The inverse scattering theory is a basic tool to solve linear differential equations and some Partial Differential Equations (PDEs). Using this theory the Korteweg-de Vries (KdV), the family of evolutionary Non Linear Schrodinger (NLS) equations, Kadomtzev-Petviashvili and many more completely integrable PDEs of mathematical physics are solved, using Zacharv-Shabath scheme. This last approach includes the use of a Lax pair, and has an advantage to be applied to wider class of equations, like difference equations, but has a disadvantage to be used only for "rapidly decreasing solutions". This technique is also intimately related to completely integrable systems. The identifying process of a Lax pair, a system and finally the "scattering data" is usually a difficult process, simplified in many cases by physicals models providing clues of how the scattering data should be chosen. In this work we show that the scattering data can be encoded into singularities of a very special mathematical object: J-unitary, identity at infinity matrix-valued function, which, if evolved once, solves the inverse scattering theory, if evolved twice solves evolutionary PDEs. The provided scheme seems to be universal in the sense that many (if not all) completely integrable PDEs arise (or should arise) in this manner by changing the so called "vessel parameters" (for examples, solutions of KdV and evolutionary NLS equations are presented). The results presented here allow to study different flows (commuting and non-commuting) in a unified approach and provide a rich mathematical arsenal to study these equations. The results are easily generalized to completely integrable PDEs of n (may be infinity) variables.

Using Gelfand-Levitan theory on a half line, we construct a vessel for the class of potentials, whose spectral functions satisfy a certain regularity assumption. When the singular part of the spectral measure is absent, we construct a canonical model of the vessel. Finally, evolving the constructed vessel, we solve the Korteweg de Vries equation on the half line, coinciding with the given potential for $t=0$. It is shown that the initial value for x=0 is prescribed by this construction, but can be perturbed using an "orthogonal" to the problem measure. The results, presented in this work 1. include formulas for the ingredients of the Gelfand-Levitan equation, 2. are shown to be general in the sense that NLS, Canonical systems and many more equations can be solved using theory of vessels, analogously to Zacharov-Shabath scheme, 3. present a generalized inverse scattering theory on a line for potentials with singularities using pre-vessels, 4. present the tau function and its role.

In this work we present a scheme for construction of solutions for evolutionary PDEs of some polynomial types q'_t = P(q,q'_x,...), where P is a polynomial in a finite number of variables. This scheme is a generalization of the existing technique for solution of completely integrable PDEs using Inverse Scattering of the Sturm-Liouville differential equation. The KdV equation q'_t = - 3/2 q q'_x + 1/4 q"'_{xxx} is a special case, corresponding to type 1 evolutionary equations. We present a complete solution of type 0, and present a KdV hierarchy corresponding to infinite number of polynomial evolutionary equations rather for \beta = 1/2 \int_0^x q(y,t)dy then for q(x,t) itself, of the form \beta'_t = i^n b_n(\beta_x'), where b_0 = -1/4 \beta"'_{xxx} + 3/2 (\beta'_x)^2 corresponds to the KdV equation and 4 (b_{n+1})'_x = -i (b_n)_{xxx}"' + 4i (\beta'_xb_n)'_x. Soliton solutions (i.e. involving pure exponents only) are presented for each such evolutionary equation, demonstrating a "simplicity" of the solutions construction.

We prove the existence of solutions to the Sturm-Liouville (SL) equation -y"(x)+q(x)y(x) = s^2 y(x) with periodic and quasi-periodic potential q(x) using theory of SL vessels, implementing a Backlund transformation of SL equation. In this paper quasi-periodic means a finite sum of periodic integrable functions. The solutions for a general s are explicitly constructed in terms of the solutions zn(x), satisfying the SL equation with initial conditions zn(0)=0, zn'(0)=1 for a discrete Levinson set of numbers s=sn, n-natural number. The tau function tau(x) of the corresponding vessel realizes the given potential via the formula q(x)= - 2(ln(tau(x)))". We also prove an analogue of the inverse scattering theorem in this setting too. Using the notion of "KdV evolutionary vessel", we construct a solution of the Korteweg-de-Vries (KdV) equation q'_t = - 3/2 q q'_x + 1/4 q"'_{xxx}, which coincides for t=0 with a given (periodic or quasi-periodic) potential., Comment: This paper has been withdrawn by the author due to a crucial error in formulas

In this work we present a new method for solving of the Korteweg-de Vries (KdV) equation q'_t = - \dfrac{3}{2} q q'_x + \dfrac{1}{4} q"'_{xxx}. The proposed method is a particular case of the theory of evolutionary vessels, developed in this work. Inverse scattering of the Sturm-Liouville operator and evolution of its potential are the basic ingredients, similar to the existing methods developed by Gardner-Greene-Kruskal-Miura (1967), Zacharov-Shabbath (1974) and Peter Lax (1977). Evolutionary KdV vessel may be considered as a generalization of these previous works. The advantage of the new method is that it produces a unified approach to existing solutions of the KdV equation. For example, odd or even analytic, periodic, almost periodic solutions are shown to be particular cases of this theory. Generalizing this method we can also produce many PDEs, associated with integrable systems, in an arbitrary number of variables (in the spirit of Zakarov-Shabat).

This work is a direct continuation of the authors work arXiv:0812.3779v1. A special case of conservative overdetermined time invariant 2D systems is developed and studied. Defining transfer function of such a systems we obtain a class CI of inner functions $S(\lambda,t_2)$, which are identity for $\lambda=\infty$, satisfy certain regularity assumptions and intertwines solutions of ODEs with a spectral parameter $\lambda$. Using translation model, we prove that every function in the class CI can be realized as a transfer function of a certain vessel. The highlight of this theory is a generalization Potapov's theorem, which gives a very special formula for such a function in the form of multiplication of Blacke-Potapov products, corresponding to the discrete spectrum of certain system operator $A_1(t_2)$ and of multiplicative integral, corresponding to the continuous spectrum of $A_1(t_2)$. This theorem is proved under a slightly more restrictive assumptions, then the development of the whole theory. Namely, we suppose that the derivative of the transfer function is a continuous function of $t_2$ for almost all $\lambda$. At the last part zero/pole interpolation problem for matrix functions in CI is considered and a realization theorem of such functions appeared in arXiv:0812.3779v1 (theorem 8.1) is reproved. Hermitian case is also analyzed and the corresponding realization theorem is proved., Comment: 54 pages

In this work we develop a theory of Vessels. This object arises in the study of overdetermined 2D systems invariant in one of the variables, which are usually called time invariant. To each overdetermined time invariant 2D systems there is associated a vessel, which is a collection of system operators satisfying certain relations and vise versa. Such an invariance forces the theory of vessels to resemble a constant (classical) 1D case and as a result many notions are naturally redefined and most theorems are reproved in this setting. The notion of transfer function and its connection to the overdetermined 2D time invariant system (and the corresponding vessel) is one of the topics of this work. It is well known that multiplicative structure of a transfer function of a 1D system is closely connected to the decomposition of the state space into invariant subspaces of the state operator and we generalize this result to a wider class of functions. This class (denoted by $\boldsymbol {\mathcal I}$) arises as a class of transfer functions, which intertwine solutions of ODEs with spectral parameters. At the end we present solution of factorization problems for finite dimensional case., Comment: 39 pages