Systolic finite field multiplier over <inline-formula> <tex-math notation="LaTeX">GF(2^{m}) </tex-math></inline-formula>, because of its superior features such as high throughput and regularity, is ...highly desirable for many demanding cryptosystems. On the other side, however, obtaining high-performance systolic multiplier with relatively low hardware cost is still a challenging task due to the fact that the systolic structure usually involves large area complexity. Based on this consideration, in this paper, we propose to carry out two novel coherent interdependent efforts. First, a new digit-serial multiplication algorithm based on polynomial basis over binary field <inline-formula> <tex-math notation="LaTeX">(GF(2^{m})) </tex-math></inline-formula> is proposed. Novel Toeplitz matrix-vector product (TMVP)-based decomposition strategy is employed to derive an efficient subquadratic space complexity. Second, The proposed algorithm is then innovatively mapped into a low-complexity systolic multiplier, which involves less area-time complexities than the existing ones. A series of resource optimization techniques also has been applied on the multiplier which optimizes further the proposed design (it is the first report on digit-serial systolic multiplier based on TMVP approach covering all irreducible polynomials, to the best of our knowledge). The following complexity analysis and comparison confirm the efficiency of the proposed multiplier, that is, it has lower area-delay product (ADP) than the existing ones. The extension of the proposed multiplier for bit-parallel implementation is also considered in this paper.
In the current work, we study the eigenvalue distribution results of a class of non-normal matrix-sequences which may be viewed as a low rank perturbation, depending on a parameter β>1, of the basic ...Toeplitz matrix-sequence {Tn(eiθ)}n∈N, i2=−1. The latter of which has obviously all eigenvalues equal to zero for any matrix order n, while for the matrix-sequence under consideration we will show a strong clustering on the complex unit circle. A detailed discussion on the outliers is also provided. The problem appears mathematically innocent, but it is indeed quite challenging since all the classical machinery for deducing the eigenvalue clustering does not cover the considered case. In the derivations, we resort to a trick used for the spectral analysis of the Google matrix plus several tools from complex analysis. We only mention that the problem is not an academic curiosity and in fact stems from problems in dynamical systems and number theory. Additionally, we also provide numerical experiments in high precision, a distribution analysis in the Weyl sense concerning both eigenvalues and singular values is given, and more results are sketched for the limit case of β=1.
The eigenvalues of Toeplitz matrices Tn(f) with a real-valued generating function f, satisfying some conditions and tracing out a simple loop over the interval −π,π, are known to admit an asymptotic ...expansion with the formλj(Tn(f))=f(σj,n)+c1(σj,n)h+c2(σj,n)h2+O(h3), where h=1/(n+1), σj,n=πjh, and ck are some bounded coefficients depending only on f. The numerical results presented in the literature suggest that the effective conditions for the expansion to hold are weaker and reduce to a fixed smoothness and to having only two intervals of monotonicity over −π,π.
In this article we investigate the superposition caused over this expansion, when considering the following linear combinationλj(Tn(f0)+βn,1Tn(f1)+βn,2Tn(f2)), where βn,1,βn,2 are certain constants depending on n and the generating functions f0,f1,f2 are either simple loop or satisfy the weaker conditions mentioned before.
We formally obtain an asymptotic expansion in this setting under simple-loop related assumptions, and we show numerically that there is much more to investigate, opening the door to linear in time algorithms for the computation of eigenvalues of large matrices of this type including a multilevel setting.
The problem is of concrete interest, considering spectral features of matrices stemming from the numerical approximation of standard differential operators and distributed order fractional differential equations, via local methods such as Finite Differences, Finite Elements, and Isogeometric Analysis.
In this note, we revisit the result of the Toeplitz matrix inversion formula proposed by Lv and Huang (2007), then we give a new structured perturbation analysis, which is useful for testing the ...stability of practical algorithms. It has been shown that our new upper bound is much sharper than the one they have given, especially when the size of the Toeplitz matrix is very large. Numerical experiments illustrate the effectiveness of our theoretical results.
Coprime arrays can achieve an increased number of degrees of freedom by deriving the equivalent signals of a virtual array. However, most existing methods fail to utilize all information received by ...the coprime array due to the non-uniformity of the derived virtual array, resulting in an inevitable estimation performance loss. To address this issue, we propose a novel virtual array interpolation-based algorithm for coprime array direction-of-arrival (DOA) estimation in this paper. The idea of array interpolation is employed to construct a virtual uniform linear array such that all virtual sensors in the non-uniform virtual array can be utilized, based on which the atomic norm of the second-order virtual array signals is defined. By investigating the properties of virtual domain atomic norm, it is proved that the covariance matrix of the interpolated virtual array is related to the virtual measurements under the Hermitian positive semi-definite Toeplitz condition. Accordingly, an atomic norm minimization problem with respect to the equivalent virtual measurement vector is formulated to reconstruct the interpolated virtual array covariance matrix in a gridless manner, where the reconstructed covariance matrix enables off-grid DOA estimation. Simulation results demonstrate the performance advantages of the proposed DOA estimation algorithm for coprime arrays.
Starting from measured data, we develop a method to compute the fine structure of the spectrum of the Koopman operator with rigorous convergence guarantees. The method is based on the observation ...that, in the measure-preserving ergodic setting, the moments of the spectral measure associated to a given observable are computable from a single trajectory of this observable. Having finitely many moments available, we use the classical Christoffel–Darboux kernel to separate the atomic and absolutely continuous parts of the spectrum, supported by convergence guarantees as the number of moments tends to infinity. In addition, we propose a technique to detect the singular continuous part of the spectrum as well as two methods to approximate the spectral measure with guaranteed convergence in the weak topology, irrespective of whether the singular continuous part is present or not. The proposed method is simple to implement and readily applicable to large-scale systems since the computational complexity is dominated by inverting an N×N Hermitian positive-definite Toeplitz matrix, where N is the number of moments, for which efficient and numerically stable algorithms exist; in particular, the complexity of the approach is independent of the dimension of the underlying state-space. We also show how to compute, from measured data, the spectral projection on a given segment of the unit circle, allowing us to obtain a finite approximation of the operator that explicitly takes into account the point and continuous parts of the spectrum. Finally, we describe a relationship between the proposed method and the so-called Hankel Dynamic Mode Decomposition, providing new insights into the behavior of the eigenvalues of the Hankel DMD operator. A number of numerical examples illustrate the approach, including a study of the spectrum of the lid-driven two-dimensional cavity flow.
In this paper we consider pentadiagonal (n+1)×(n+1) matrices with two sub-diagonals above and below the main diagonal at distances k and ℓ from the main diagonal where 1≤k<ℓ≤n. We give explicit ...formulae for the eigenpairs of imperfect Toeplitz matrices in the case when (n+1)/2≤k. Imperfectness means that the first and last k elements of the main diagonal differ from the elements in the middle.
Generalized digamma functions ψk(x), studied by Ramanujan, Deninger, Dilcher, Kanemitsu, Ishibashi etc., appear as the Laurent series coefficients of the Hurwitz zeta function. In this paper, a ...modular relation of the form Fk(α)=Fk(1/α) containing infinite series of ψk(x), or, equivalently, between the generalized Stieltjes constants γk(x), is obtained for any k∈N. When k=0, it reduces to a famous transformation given on page 220 of Ramanujan's Lost Notebook. For k=1, an integral containing Riemann's Ξ-function, and corresponding to the aforementioned modular relation, is also obtained along with its asymptotic expansions as α→0 and α→∞. Carlitz-type and Guinand-type finite modular relations involving ψj(m)(x),0≤j≤k,m∈N∪{0}, are also derived, thereby extending previous results on the digamma function ψ(x). The extension of Guinand's result for ψj(m)(x),m≥2, involves an interesting combinatorial sum h(r) over integer partitions of 2r into exactly r parts. This sum plays a crucial role in an inversion formula needed for this extension. This formula has connection with the inversion formula for the inverse of a triangular Toeplitz matrix. The modular relation for ψj′(x) is subtle and requires delicate analysis.
PDF
