Search

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem are also closely related to fast algorithms for other natural algebraic questions such as polynomial factorization and modular composition. And while nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck [7], fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state-of-the-art for this problem, Umans [25] and Kedlaya & Umans [16] gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields, respectively, provided that the number of variables n is at most do(1) where the degree of the input polynomial in every variable is less than d. They also stated the question of designing fast algorithms for the large variable case (i.e., n x do(1)) as an open problem. In this work, we show that there is a deterministic algorithm for multivariate multipoint evaluation over a field Fq of characteristic p, which evaluates an n-variate polynomial of degree less than d in each variable on N inputs in time provided that p is at most do(1), and q is at most (exp(exp(exp(· · · (exp(d))))), where the height of this tower of exponentials is fixed. When the number of variables is large (e.g., n x do(1)), this is the first nearly linear time algorithm for this problem over any (large enough) field. Our algorithm is based on elementary algebraic ideas, and this algebraic structure naturally leads to the following two independently interesting applications: --We show that there is an algebraic data structure for univariate polynomial evaluation with nearly linear space complexity and sublinear time complexity over finite fields of small characteristic and quasipolynomially bounded size. This provides a counterexample to a conjecture of Miltersen [21] who conjectured that over small finite fields, any algebraic data structure for polynomial evaluation using polynomial space must have linear query complexity. We also show that over finite fields of small characteristic and quasipolynomially bounded size, Vandermonde matrices are not rigid enough to yield size-depth tradeoffs for linear circuits via the current quantitative bounds in Valiant's program [26]. More precisely, for every fixed prime p, we show that for every constant e > 0, and large enough n, the rank of any n × n Vandermonde matrix V over the field Fpa can be reduced to (n/exp(O(poly(e)log0.53 n))) by changing at most nT(e) entries in every row of V, provided a = poly(logn). Prior to this work, similar upper bounds on rigidity were known only for special Vandermonde matrices. For instance, the Discrete Fourier Transform matrices and Vandermonde matrices with generators in a geometric progression [9]. [ABSTRACT FROM AUTHOR]

We prove that the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems over the cyclotomic field Q (ζ n) are not equivalent. Precisely, we show that reducing one problem to the other increases the noise by a factor that is more than polynomial in n. We do so by providing a lower bound, holding for infinitely many positive integers n, for the condition number of the Vandermonde matrix of the nth cyclotomic polynomial. [ABSTRACT FROM AUTHOR]

In this paper, the H∞$$ {H}_{\infty } $$ saturated control problems of networked systems with random sampling periods and stochastic transmission delays are investigated. The main issue is to design an H∞$$ {H}_{\infty } $$ saturated controller such that the controlled close‐loop system is exponentially mean‐square stable with a desired H∞$$ {H}_{\infty } $$ performance. A matrix exponential which is different from some existing literature is used to reconstruct the discrete‐time stochastic system to an equivalent yet tractable augmented model without any additional conditional constraint. In virtue of reduced‐order confluent Vandermonde matrix approach and Kronecker product operation, the stability condition in terms of linear matrix inequality is derived and then the desired H∞$$ {H}_{\infty } $$ saturated controller is designed. It should be emphasized that the improved method can also be used for the stability analysis and controller design when the system matrix contains complex roots. Finally, two numerical examples and a three‐axis milling machine system are utilized to manifest the reliability and practicality of the designed strategy. [ABSTRACT FROM AUTHOR]

The approach to solving linear systems with structured matrices by means of the bidiagonal factorization of the inverse of the coefficient matrix is first considered in this review article, the starting point being the classical Björck–Pereyra algorithms for Vandermonde systems, published in 1970 and carefully analyzed by Higham in 1987. The work of Higham briefly considered the role of total positivity in obtaining accurate results, which led to the generalization of this approach to totally positive Cauchy, Cauchy–Vandermonde and generalized Vandermonde matrices. Then, the solution of other linear algebra problems (eigenvalue and singular value computation, least squares problems) is addressed, a fundamental tool being the bidiagonal decomposition of the corresponding matrices. This bidiagonal decomposition is related to the theory of Neville elimination, although for achieving high relative accuracy the algorithm of Neville elimination is not used. Numerical experiments showing the good behavior of these algorithms when compared with algorithms that ignore the matrix structure are also included. [ABSTRACT FROM AUTHOR]

In this paper we present a concrete algebraic construction of a novel class of convolutional codes. These codes are built upon generalized Vandermonde matrices and therefore can be seen as a natural extension of Reed–Solomon block codes to the context of convolutional codes. For this reason we call them weighted Reed–Solomon (WRS) convolutional codes. We show that under some constraints on the defining parameters these codes are Maximum Distance Profile (MDP), which means that they have the maximal possible growth in their column distance profile. We study the size of the field needed to obtain WRS convolutional codes which are MDP and compare it with the existing general constructions of MDP convolutional codes in the literature, showing that in many cases WRS convolutional codes require significantly smaller fields. [ABSTRACT FROM AUTHOR]

In this paper, we first give the definition of the Euclidean sums of linear codes, and prove that the Euclidean sums of linear codes are Euclidean dual-containing. Then we construct two new classes of optimal asymmetric quantum error-correcting codes based on Euclidean sums of the Reed-Solomon codes, and two new classes of optimal asymmetric quantum error-correcting codes based on Euclidean sums of linear codes generated by Vandermonde matrices over finite fields. Moreover, these optimal asymmetric quantum errorcorrecting codes constructed in this paper are different from the ones in the literature. [ABSTRACT FROM AUTHOR]

The ability to sense propagating electromagnetic plane waves based on their directions of arrival (DOAs) is fundamental to a range of radio frequency (RF) sensing, communications, and imaging applications. This paper introduces an algorithm for the wideband true time delay digital delay Vandermonde matrix (DVM), utilizing Thiran fractional delays that are useful for realizing RF sensors having multiple look DOA support. The digital DVM algorithm leverages sparse matrix factorization to yield multiple simultaneous RF beams for low-complexity sensing applications. Consequently, the proposed algorithm offers a reduction in circuit complexity for multi-beam digital wideband beamforming systems employing Thiran fractional delays. Unlike finite impulse response filter-based approaches which are wideband but of a high filter order, the Thiran filters trade usable bandwidth in favor of low-complexity circuits. The phase and group delay responses of Thiran filters with delays of a fractional sampling period will be demonstrated. Thiran filters show favorable results for sample delay blocks with a temporal oversampling factor of three. Thiran fractional delays of orders three and four are mapped to Xilinx FPGA RF-SoC technologies for evaluation. The preliminary results of the APF-based Thiran fractional delays on FPGA can potentially be used to realize DVM factorizations using application-specific integrated circuit (ASIC) technology. [ABSTRACT FROM AUTHOR]

Let r be any real number and for any n let p1,...., pn be distinct positive numbers. A Kwong matrix is the n x n matrix whose (i, j) entry is (pri +prj)/(pi +pj). We determine the signatures of eigenvalues of all such matrices(The corresponding problem for the family of Loewner matrices [(pri +prj)/(pi - pj)] has been solved earlier. [ABSTRACT FROM AUTHOR]

Here, a novel image‐based quantized compressive sensing (QCS) framework based on complex‐valued Vandermonde (Vander) matrix is proposed. In the proposed QCS framework, a discrete wavelet transform (DWT) serves as a sparse basis and a partial complex‐valued Vander matrix serves as a measurement matrix. The theoretical analysis based on mutual coherence metric of compressive sensing (CS) theory shows that the proposed Vander measurement matrix has the best reconstruction performance among other conventional measurement matrices. The simulation results also show that the recovery quality using the proposed measurement matrix can be greatly improved compared with the other existing real‐valued measurement matrices. In particular, the experiment results also show that under the same measurement matrix, the reconstruction performance of Smoothed l0 norm (SL0) algorithm is better than that of Orthogonal Matching Pursuit (OMP) algorithm, sparsity adaptive matching pursuit (SAMP) algorithm and approximate message passing (AMP) algorithm. In addition, a sparse measurement matrix scheme is further proposed to achieve a trade‐off between recovery performance and computational complexity. The theoretical analysis and simulation results both show the proposed image‐based QCS is efficient. [ABSTRACT FROM AUTHOR]

This paper establishes the linear algebra of the (r, β)-Stirling matrix. Along the way, this paper derives various identities, such as its factorization and relationship to the Pascal matrix and the Stirling matrix of the second kind. Additionally, this paper develops a natural extension of the Vandermonde matrix, which can be used to study and evaluate successive power sums of arithmetic progressions. [ABSTRACT FROM AUTHOR]

The article discusses the Cauchy matrix and its various properties and applications. It presents a theorem and provides a new proof for it, along with a lemma that aids in the proof. The text also discusses a mathematical proof involving matrices and summation notation, demonstrating a property of matrix multiplication. It introduces Theorem 1, which states that the sum of all entries of the inverse matrix is equal to the sum of all entries of the original matrix. The text also mentions a variant of Theorem 1 and introduces Theorem 4, which relates to a modified matrix. Additionally, the text discusses a theorem and its proof sketch regarding the calculation of determinants. It concludes with propositions regarding the inverse and determinant of a matrix obtained from another matrix by replacing certain elements. The text also includes a note from the publisher expressing neutrality. [Extracted from the article]

We study the problem of super-resolution of a linear combination of Dirac distributions and their derivatives on a one-dimensional circle from noisy Fourier measurements. Following numerous recent works on the subject, we consider the geometric setting of "partial clustering", when some Diracs can be separated much below the Rayleigh limit. Under this assumption, we prove sharp asymptotic bounds for the smallest singular value of a corresponding rectangular confluent Vandermonde matrix with nodes on the unit circle. As a consequence, we derive matching lower and upper min-max error bounds for the above super-resolution problem, under the additional assumption of nodes belonging to a fixed grid. [ABSTRACT FROM AUTHOR]

The canonical polyadic decomposition (CPD) of higher-order tensors, a.k.a. PARAFAC, has shown excellent performance in two-dimensional direction of arrival (DOA) estimation using the acoustic vector sensor array (AVSA). However, most existing studies pay little attention to the manifold matrix structure of the AVSA during the CPD and are designed for uncorrelated sources. This paper presents a constrained CPD-based algorithm for DOA estimation using a uniform linear AVSA, whose manifold matrix is highly structured. Specifically, the manifold matrix equals to the Khatri-Rao product of a Vandermonde matrix and a proportional column-norm matrix. We show that DOA estimation accuracy is further improved by incorporating the prior structured information. Besides, we also extend the Toeplitz decorrelation technique to the AVSA to handle possibly correlated sources. The algorithm does not require iteration or peak searching and thus is computationally effective. Numerical simulations verify the effectiveness and superior performance of the algorithm. [ABSTRACT FROM AUTHOR]

For coded distributed computing (CDC), polynomial code is one prevalent encoding method for CDC (called Poly-CDC). It suffers from poor numerical stability due to the Vandermonde matrix serving as the coefficient matrix which needs to be inverted, and whose condition number increases exponentially with the size of the matrix or equivalently with the number of parallel worker nodes. To improve the numerical stability, especially for large networks, we propose a Newton-like polynomial code (NLPC)-based CDC (NLPC-CDC), with a design dedicated for both matrix–vector and matrix–matrix multiplications. The associated proof of the constructed code possesses a (n , k) -symmetrical combination property (CP), where symmetrical means the worker nodes have identical computation volume, CP means the k-symmetrical original computing tasks are encoded into n (n ≥ k) -symmetrically coded computing tasks, and the arbitrary k resulting from the n-coded computing tasks can recover the intended computing results. Extensive numerical studies verify the significant numerical stability improvement of our proposed NLPC-CDC over Poly-CDC. [ABSTRACT FROM AUTHOR]

The huge bandwidth and immunity to electromagnetic interference make visible light communication (VLC) systems the preferred technique for many applications. Unfortunately, the superposition of multiple subcarriers in VLC orthogonal frequency division multiplexing systems leads to a high peak-to-average power ratio (PAPR). So, in this study, we aim to reduce PAPR in VLC systems and improve the system performance by proposing non-distorting PAPR reduction techniques like precoding techniques as it doesn't affect the system data rate because they do not require any obligatory transmission of side information. Moreover, it has a very good ability to reduce the PAPR without affecting the system BER performance. So, different precoding reduction techniques are proposed like discrete cosine transform (DCT), discrete sine transform (DST), discrete Hatley transform (DHT), and Vandermonde like matrix (VLM), to address the high PAPR and light-emitting diode-restricted linear range problems in VLC systems. The proposed technique using DHT, DCT, DST, and VLM provided a significant advantage in reducing the PAPR by 1.35 dB, 1.46 dB, 2.12 dB, and 2.17 dB, respectively. So the proposed technique is based on using the VLM precoding technique to achieve maximum reachable PAPR reduction value. Also, a comparison of the presented work and related literature reviews for PAPR reduction techniques are held to ensure the validity and effectiveness of the proposed scheme. [ABSTRACT FROM AUTHOR]

Let F be a field and let F (X 1 , ... , X n) be the field of rational functions in n variables X 1 , ... , X n over F. Let T = X 1 + ⋯ + X n ∈ F (X 1 , ... , X n) and let m be a positive integer such that char F ∤ m. Is it possible to express each X i as a rational function in X 1 m ... , X n m and T over F? It is not difficult to prove that this can be done but it is another matter to show how this is done. We answer the above question affirmatively with a nonconstructive proof and a constructive proof. [ABSTRACT FROM AUTHOR]

Consider the method of fundamental solutions (MFS) for 2D Laplace's equation in a bounded simply connected domain S$$ S $$. In the standard MFS, the source nodes are located on a closed contour outside the domain boundary Γ(=∂S)$$ \Gamma \left(=\partial S\right) $$, which is called pseudo‐boundary. For circular, elliptic, and general closed pseudo‐boundaries, analysis and computation have been studied extensively. New locations of source nodes are proposed along two pseudo radial‐lines outside Γ$$ \Gamma $$. Numerical results are very encouraging and promising. Since the success of the MFS mainly depends on stability, our efforts are focused on deriving the lower and upper bounds of condition number (Cond). The study finds stability properties of new Vandermonde‐wise matrices on nodes xi∈[a,b]$$ {x}_i\in \left[a,b\right] $$ with 0

We consider Lagrange interpolation with Spherical Harmonics of data located at the equiangular Cubed Sphere nodes. An approach based on a suitable Echelon Form of the associated Vandermonde matrix is carried out. As an outcome, a particular subspace of Spherical Harmonics is defined. This subspace possesses a high-frequency truncation, reminiscent of the rhomboidal truncation. Numerical results show the interest of this approach in various contexts. In particular, several examples of resolution of the Poisson equation on the sphere are displayed. [ABSTRACT FROM AUTHOR]

In this work, we set up the generating function of the ultimate time survival probability φ(u + 1), where... ...is positive for all n ∈ N, where a certain growth is illustrated by the deterministic part u + κn and decrease is given by the subtracted random partPni=1 Xi. Based on the proven theoretical statements, we give several examples of φ(u) and its generating function expressions, when random variables Xi admit Bernoulli, geometric and some other distributions. [ABSTRACT FROM AUTHOR]

In water- and wastewater-treatment processes, knowledge of sludge settlement behavior is a key requirement for proper design of a continuous clarifier or thickener. One of the most robust and practical tests to acquire information about rate of sedimentation is through execution of batch settling tests. In lieu of conducting a series of settling tests for various initial concentrations, it is promising and advantageous to develop simple predictive models to estimate the sludge settlement behavior for a wide range of operating conditions. These predictive mathematical model(s) also enhance the accuracy of outputs by eliminating measurement errors originated from graphical methods and visual observations. In the present study, two empirical models were proposed based on Vandermonde matrix (VM) characteristics as well as a Levenberg–Marquardt (LM) algorithm to predict temporal height of the supernatant–sludge interface. The novelty of our modeling approach is twofold: the proposed models in this study are more robust and simpler compared to other models in the literature, and the initial sludge concentration was considered as a key independent variable in addition to the more-customarily used settling time. The prediction performance of the VM-based model was better than the LM-based model considering the statistical parameters associated with the fitting of the experimental data including coefficient of determination (R2), root mean square error (RMSE), and mean absolute percentage error (MAPE). The values of R2, RMSE, and MAPE for the VM- and LM-based models were obtained at 0.997, 0.132, and 5.413% as well as 0.969, 0.107, and 6.433%, respectively. The proposed predictive models will be useful for determination of the sedimentation behavior at pilot- or industrial-scale applications of water treatment, when the experimental methods are not feasible, time is limited, or adequate laboratory infrastructure is not available. [ABSTRACT FROM AUTHOR]

A quasi-Toeplitz (QT) matrix is a semi-infinite matrix of the form A = T (a) + E where T(a) is the Toeplitz matrix with entries (T (a)) i , j = a j - i , for a j - i ∈ C , i , j ≥ 1 , while E is a matrix representing a compact operator in ℓ 2 . The matrix A is finitely representable if a k = 0 for k < - m and for k > n , given m , n > 0 , and if E has a finite number of nonzero entries. The problem of numerically computing eigenpairs of a finitely representable QT matrix is investigated, i.e., pairs (λ , v) such that A v = λ v , with λ ∈ C , v = (v j) j ∈ Z + , v ≠ 0 , and ∑ j = 1 ∞ | v j | 2 < ∞ . It is shown that the problem is reduced to a finite nonlinear eigenvalue problem of the kind W U (λ) β = 0 , where W is a constant matrix and U depends on λ and can be given in terms of either a Vandermonde matrix or a companion matrix. Algorithms relying on Newton's method applied to the equation det W U (λ) = 0 are analyzed. Numerical experiments show the effectiveness of this approach. The algorithms have been included in the CQT-Toolbox [Numer. Algorithms 81 (2019), no. 2, 741–769]. [ABSTRACT FROM AUTHOR]

The main research object of this paper is to present a systematic computational procedure for computing the inverse of a generalized Vandermonde matrix. Short and rigorous proofs for the formulas of the determinant and the inverse of a generalized Vandermonde matrix are proposed. The computational cost of this method is O (n 2) . The proposed method can be used efficiently for hand calculation as well as for computer programming. Some examples are given for the sake of illustration. Furthermore, we present a simulation study to compare the time spent to calculate the inverse using the proposed algorithm and the inverse function in Maple. [ABSTRACT FROM AUTHOR]

In this paper, a novel method is presented to compute an explicit formula for the inverse of the confluent Vandermonde matrices. The proposed results may have many interesting perspectives in diverse areas of mathematics and natural sciences, notably on the situations where the Vandermonde matrices have acquired much usefulness. The method presented here is direct and straightforward, it gives explicit and compact formulas. Several examples are presented to highlight the results. The main tools are some elementary basic linear algebra. [ABSTRACT FROM AUTHOR]

We investigate the size of the largest entry (in absolute value) in the inverse of certain Vandermonde matrices. More precisely, for every real b > 1 , let M b (n) be the maximum of the absolute values of the entries of the inverse of the n × n matrix [ b i j ] 0 ≤ i , j < n . We prove that lim n → + ∞ M b (n) exists, and we provide some formulas for it. [ABSTRACT FROM AUTHOR]

in this work, we present an advanced interpolation method via the Vandermonde matrix for solving weakly singular Volterra integral equations of the second kind. The optimal rules for the node distributions of the two kernel variables were created to guarantee that the kernel's singularity was isolated. The unknown function is interpolated using three matrices: one of which is the monomial matrix, based on the Vandermonde matrix and Chebyshev nodes; the second is the known square Vandermyde matrix, and the third is the unknown coefficient matrix. The singular kernel is interpolated twice and transformed into a double-interpolated non-singular function through five matrices, two of which are monomials. A linear algebraic system can be obtained without using the collocation points by inserting the interpolated unknown function on the left and right sides of the integral equation. The solution of the obtained system yields the unknown coefficients matrix and thereby finds the interpolated solution. The obtained results from solving six examples are faster to converge to the exact ones using the lowest degree of interpolants and are better than those achieved by the other indicated method, which confirms the novelty and efficiency of the presented method. [ABSTRACT FROM AUTHOR]

In this work, multiplicities of zeros of skew polynomials are studied. Two distinct definitions are considered: First, a is said to be a zero of F of multiplicity r if (x − a) r divides F on the right; second, a is said to be a zero of F of multiplicity r if some skew polynomial P = (x − a r) ⋯ (x − a 2) (x − a 1) , having a 1 = a as its only right zero, divides F on the right. Neither of these two notions implies the other for general skew polynomials. We show that, in the first case, Lam and Leroy's concept of P-independence does not behave naturally, whereas a union theorem still holds. In contrast, we show that P-independence behaves naturally for the second notion of multiplicities. As a consequence, we provide extensions of classical commutative results to general skew polynomials. These include: (1) The upper bound on the number of (P-independent) zeros (counting multiplicities) of a skew polynomial by its degree, and (2) The equivalence of P-independence, Hermite interpolation and the invertibility of confluent Vandermonde matrices (for which we introduce skew polynomial Hasse derivatives). [ABSTRACT FROM AUTHOR]

The spatial smoothing-based and matrix reconstruction-based decorrelation algorithms are widely used to realize the accurate direction-of-arrival (DOA) estimation with the coexistence of both uncorrelated and coherent sources. However, these methods apply only to the traditional uniform linear array (ULA), of which the manifold matrix is a Vandermonde structure. In this paper, to achieve the DOA estimation of mixed signals on coprime array, the coprime array is decomposed into two independent sub-ULAs, and the received data is processed, respectively. An improved spatial differencing technique is exploited to estimate the uncorrelated and coherent sources separately, and the lost degree of freedom (DOF) caused by array decomposition is recovered. The final high-precision DOA estimation is obtained by conducting an ambiguity resolution method to the estimation results of the decomposed subarrays. Furthermore, double-phase partial spectral search scheme is introduced to diminish the computational complexity. The feasibility and superiority of the proposed algorithm are validated through detailed experimental simulations. [ABSTRACT FROM AUTHOR]

Let p 1 , p 2 , ... , p n be distinct positive real numbers and m be any integer. Every symmetric polynomial f (x , y) ∈ C [ x , y ] induces a symmetric matrix f (p i , p j) i , j = 1 n. We obtain the determinants of such matrices with an aim to find the determinants of P m = (p i + p j) m i , j = 1 n and B 2 m = (p i − p j) 2 m i , j = 1 n for m ∈ N (where N is the set of natural numbers) in terms of the Schur polynomials. We also discuss and compute determinant of the matrix K m = p i m + p j m p i + p j i , j = 1 n for any integer m in terms of the Schur and skew-Schur polynomials. [ABSTRACT FROM AUTHOR]

Conventional direction-of-arrival (DOA) estimation algorithms like MUSIC only allow localization of fewer number of sources than the number of physical sensors. In this paper, underdetermined azimuth localization (localizing more sources than the number of sensors) using arbitrary planar arrays has been proposed, using only second-order statistics of the received data. To achieve this, we utilize the difference coarray of the actual array and express the elements of the array covariance matrix as the signal received by the virtual sensors of the coarray. We explore the structure and geometry of the difference coarray of an $N$ -element planar array and show that the coarray can provide an increased degree-of-freedom (DOF) of $\mathcal {O}(N^{2})$ which enables underdetermined localization. Then, we extend the manifold separation (MS) technique to the coarray to express the coarray steering matrix in terms of a Vandermonde structured matrix by designing a signal independent coarray characteristic matrix. As the signal model of a coarray is a single snapshot model, the Vandermonde structure enables us to perform a spatial smoothing type operation to restore the rank of the coarray covariance matrix. This allows us to propose a novel subspace-based algorithm, which we call the coarrayMS-MUSIC, to perform underdetermined source localization using arbitrary planar arrays. We have also introduced the polynomial rooting version of our algorithm called the coarrayMS-rootMUSIC. Finally, we have conducted extensive numerical simulations to verify the effectiveness and usefulness of the proposed methods. [ABSTRACT FROM AUTHOR]

By closely following a construction by Ganelius, we use Faber rational functions to derive tight explicit bounds on Zolotarev numbers. We use our results to bound the singular values of matrices, including complex-valued Cauchy matrices and Vandermonde matrices with nodes inside the unit disk. We construct Faber rational functions using doubly connected conformal maps and use their zeros and poles to supply shift parameters in the alternating direction implicit method. [ABSTRACT FROM AUTHOR]

Blaum–Roth Codes are binary maximum distance separable (MDS) array codes over the binary quotient ring F 2 [ x ] / (M p (x)) , where M p (x) = 1 + x + ⋯ + x p − 1 , and p is a prime number. Two existing all-erasure decoding methods for Blaum–Roth codes are the syndrome-based decoding method and the interpolation-based decoding method. In this paper, we propose a modified syndrome-based decoding method and a modified interpolation-based decoding method that have lower decoding complexity than the syndrome-based decoding method and the interpolation-based decoding method, respectively. Moreover, we present a fast decoding method for Blaum–Roth codes based on the LU decomposition of the Vandermonde matrix that has a lower decoding complexity than the two modified decoding methods for most of the parameters. [ABSTRACT FROM AUTHOR]

Non-Orthogonal Multiple Access (NOMA) is an ideal choice for 5G waveforms due to their characteristics such as high data rate, massive device connectivity, high spectral access, and effective frequency selective fading. Thus, it permits gigantic connectivity. The spectrum overlaps with NOMA, which consents several operators to segment the spectrum at the same frequency. These features make NOMA more suitable for use beyond 5G. Peak to Average Power (PAPR) is a major problem in Multi-Carrier Techniques (MCT) like NOMA and it also degrades the performance of the amplifier. The Partial Transmission Sequence (PTS) is a superior algorithm for moderating the PAPR. However, it also increases the complexity of the structure. The PAPR is reduced in NOMA by multiplying the NOMA signal with optimised phase vectors (P). The phase vectors are generated by using the Vandermonde Matrix (VM). In this work, we proposed a VM-PTS algorithm for the NOMA system, and the number of computations to search the optimal phase vectors for NOMA high PAPR signal is less as compared with existing PTS. The outcomes demonstrate that the performance of the recommended PTS in terms of PAPR, Bit Error Rate (BER), and complexity is better than the conventional PTS (C-PTS). [ABSTRACT FROM AUTHOR]

We state and prove an explicit evaluation of a certain multi-variate integral and use it to furnish a new, and shorter, proof of an elegant determinant identity of Michael Dougherty and Jon McCammond that came up in their study of critical values of a complex polynomial. [ABSTRACT FROM AUTHOR]

• The problem of Vandermonde constrained CP tensor decomposition for angle estimation in MIMO radar under spatially colored noise is addressed. • The smoothed estimate of the temporal cross-correlation matrix is presented to provide improved robustness to colored noise in the case of the limited number of pulses. • Constrained alternating least squares (ALS) based on new rectification strategy for Vandermonde factors is used to solve CP decomposition model. • With the help of temporally smoothed cross-correlation and constrained ALS, the proposed method exhibits superior angle estimation performance. We address the problem of Vandermonde constrained CANDECOMP/PARAFAC (CP) tensor decomposition in application to angle estimation for bistatic multiple-input multiple output (MIMO) radar under spatially colored noise. By exploiting the temporally uncorrelated characteristic of colored noise, a new denoising scheme based on the temporally smoothed cross-correlation approach is presented. Then, after rearranging the smoothed cross-correlation matrix into a fourth-order tensor, a Vandermonde constrained CP tensor decomposition model is formulated, which fully exploits the multidimensional structure of the array measurement and the Vandermonde structure of the factor matrices. To solve this model, an efficient constrained alternating least squares (ALS) algorithm is developed to decompose the Vandermonde factor matrices. Finally, joint estimates of direction of departure (DOD) and direction of arrival (DOA) are obtained by the generators of the Vandermonde factor matrices. Compared with the state-of-the-art approaches, the proposed method can achieve better angle estimation performance by jointly using the temporally smoothed cross-correlation denoising operation and enforcing the Vandermonde structure information in the tensor decomposition. Numerical simulation results verify the effectiveness and improvement of our algorithm. [ABSTRACT FROM AUTHOR]

An integer-forcing linear receiver has significantly better performance than conditional receivers for slow-fading channels because it directly recovers an integer linear combination of signals instead of decoding all signals. The performance in terms of achievable rate, outage probability, and error rate can be improved with a unitary matrix precoder imposed at each channel realization. In this paper, a new special unitary matrix precoding approach is proposed to reduce the computational complexity. Different from the parameterization technique with many parameters, the new method constructs a unitary Vandermonde matrix with only a single parameter. The optimal Vandermonde matrix is determined on the basis of the shortest vector of a lattice generated by the precoding matrix in which the single parameter is searched. Therefore, its complexity is reduced to a polynomial time, whereas the traditional unitary precoder has exponential complexity. Simulation results show that the proposed scheme can achieve the performance similar to the benchmark schemes but with much lower complexity. The scheme offers a good trade-off between performance and complexity. [ABSTRACT FROM AUTHOR]

A block code is called a locally recoverable code (LRC for short) with $(r,\delta)$ -locality, if subject to any $\delta -1$ erasure failures, every symbol in the encoding can still be recovered by accessing at most $r$ other symbols. Recently, it was discovered by several authors that a $q$ -ary optimal $(r,\delta)$ -LRC, i.e., an LRC achieving the generalized Singleton-type bound, can have length much bigger than $q+1$. This is quite different from the classical $q$ -ary MDS codes where it is conjectured that the code length is upper bounded by $q+1$ (or $q+2$ for some special cases). In this paper, we further investigate constructions of optimal $(r,\delta)$ -LRCs along the line of using parity-check matrices. Inspired by classical Reed-Solomon codes and the work in Jin (2019), we equip parity-check matrices with the Vandermonde structure. It turns out that a parity-check matrix with the Vandermonde structure that produces an optimal LRC must obey certain disjoint property for subsets of $\mathbb {F}_{q}$. We manage to show the existence of these disjoint subsets. Thus, this yields an optimal $(r,\delta)$ -LRC with code length $\Omega \left({q^{\frac {\delta }{2}\left({1+\frac {1}{\lfloor \frac {d-1}{\delta }\rfloor -1}}\right)}}\right)\vphantom {\bigg)_{j}}$ , where $d$ is the minimum distance. In particular, to our surprise, for $\delta =2$ this disjoint condition is equivalent to a well-studied problem in extremal graph theory. With the help of extremal graph theory, we succeed to improve all of the best known results in Guruswami et al. (2018) for $d\geq 7$. In addition, for $d=6$ , we are able to remove the constraint required in Jin (2019) that $q$ is even. [ABSTRACT FROM AUTHOR]

We address the problem of tensor decomposition in application to direction-of-arrival (DOA) estimation for two-dimensional transmit beamspace (TB) multiple-input multiple-output (MIMO) radar. A general higher-order tensor model that enables computationally efficient DOA estimation is designed. Whereas other tensor decomposition-based methods treat all factor matrices as arbitrary, the essence of the proposed DOA estimation method is to fully exploit the Vandermonde structure of the factor matrices to take advantage of the shift-invariance between and within different transmit subarrays. Specifically, the received signal of TB MIMO radar is expressed as a higher-order tensor. A computationally efficient tensor decomposition method is proposed to decompose the Vandermonde factor matrices. The generators of the Vandermonde factor matrices are computed to estimate the phase rotations between subarrays, which can be utilized as a look-up table for finding target DOAs. The proposed tensor model and the DOA estimation algorithm are also straightforwardly applicable for the one-dimensional TB MIMO radar case. It is further shown that our proposed approach can be used in a more general scenario where the transmit subarrays with arbitrary but identical configuration can be non-uniformly displaced. We also show that both the tensor rank of the signal tensor and the matrix rank of a particular matrix derived from the signal tensor are identical to the number of targets. Thus, the number of targets can be estimated via matrix rank determination. Simulation results illustrate the performance improvement of the proposed DOA estimation method as compared to other tensor decomposition-based techniques for TB MIMO radar. [ABSTRACT FROM AUTHOR]

We prove explicit lower bounds for the smallest singular value and upper bounds for the condition number of rectangular, multivariate Vandermonde matrices with scattered nodes on the complex unit circle. Analogously to the Shannon-Nyquist criterion, the nodes are assumed to be separated by a constant divided by the used polynomial degree. If this constant grows linearly with the spatial dimension, the condition number is uniformly bounded. If it grows only logarithmically with the spatial dimension, the condition number can, in the worst case, grow slightly stronger than exponentially with the spatial dimension. Both results improve over all previously known results of such type and cannot be improved considerably which is shown by considering specific node sets. [ABSTRACT FROM AUTHOR]

Recently, Liu and Liu gave the Singleton bound for pure asymmetric entanglement-assisted quantum error-correcting (AEAQEC) codes. They constructed three new families of AQEAEC codes by means of Vandermonde matrices, generalized Reed-Solomon (GRS) codes and cyclic codes. In this paper, we first exhibit the Singleton bound for any AEAQEC codes. Then we construct AEAQEC codes by two distinct constacyclic codes. By means of repeated-root cyclic codes, we construct new AEAQEC MDS codes. In addition, our methods allow for easily calculating the dimensions, d z , d x and the number c of pre-shared maximally entangled states of AEAQEC codes. [ABSTRACT FROM AUTHOR]

We consider the channel estimation problem in a millimeter-wave (mmWave) multiple-input multiple-output orthogonal frequency division multiplexing (MIMO-OFDM) system aided by a passive reconfigurable intelligent surface (RIS). Initially, leveraging the inherent sparsity of mmWave channels, we decouple the channel estimation into the recovery of multipath parameters, including spatial frequencies of angles, delays, and complex gains. Subsequently, we employ two training schemes: the first involves a full row rank constrained RIS phase shift pattern, and the second incorporates a Kronecker structure constrained RIS phase shift pattern. These schemes reform channel estimation into estimating parameters from two fifth-order tensor signals, which admit constrained Canonical Polyadic decomposition. Moreover, both tensor signals share Vandermonde-constrained factor matrices, enabling algebraic algorithms for tensor decomposition problems and recovering channel multipath parameters. Theoretical analyses show that the first training scheme has a lower signal processing complexity for channel estimation, while the second attains a higher estimation accuracy. Also, we prove that our proposed two schemes have the same minimum pilot overhead, which is as low as proportional to the product of the number of paths in the two MIMO channels (transmitter-RIS and RIS-receiver). Numerical results validate the effectiveness of our proposed methods. • We propose two training schemes for RIS-assisted mmWave MIMO-OFDM systems. • We present two fifth-order tensor training signals with Vandermonde factor matrices. • We develop two algebraic algorithms for efficient channel estimation. • We analyze the minimum pilot overhead, offering practical guidance for system design. [ABSTRACT FROM AUTHOR]

• A novel numerical method based on Hartley series expansion is introduced. • New higher order finite difference scheme is introduced for the core boundary points. • Vandermonde system is solved to obtain the Hartley coefficients. • Convergence and stability of Hartley series method are studied. In this work, new accurate solutions based on Hartley series expansion for temporal calculations and higher order finite difference schemes for space derivative calculations are presented for the neutron diffusion systems. Throughout a novel use of a linear combination of Hartley series, a new temporal approximate solution is obtained. Determination of the series coefficients is a basic requirement to complete the reactor power calculations. Hartley series coefficients are determined by solving an algebraic system whose fundamental matrix is the famous Vandermonde matrix. Convergence and stability of Hartley series method is discussed. It is proved that the method is conditionally stable and a new criterion on the time step size is introduced. In previous work, we provided an accurate finite difference scheme with order of accuracy O Δ 4 by employing five point stencils in each direction with equally distance Δ at the core interior mesh points. But a large amount of the gained accuracies is lost due to using second order finite difference scheme at the core boundaries. Here, a new formula for the points adjacent to the core boundaries is derived with the same order of accuracy O Δ 4 . This procedure significantly improved the accuracy of the steady state calculations. For homogenous reactor as an example, the new scheme reduces the errors to negligible amounts. The results are tested for the well-known benchmark transient problems such homogenous, TWIGL and LRA-BWR reactor cores for validation purposes. These cores are divided into just a few dozens or hundreds of fuel assemblies. Then, we compared our results with those obtained recently by the Improved SIDK, FLUENT, TASNAM and BRBFCM methods that divided the same reactor core into thousands of meshes by using mesh generation tools such GAMBIT and ICEM-CFD. [ABSTRACT FROM AUTHOR]

Let R : = F [ x ; σ , δ ] be a multivariate skew polynomial ring over a division ring F. In this paper, we introduce the notion of right and left (σ , δ) -partial derivatives of polynomials in R and we prove some of their main properties. As an application of these results, we solve in R a Hermite-type multivariate skew polynomial interpolation problem. The main technical tools and results used here are of constructive type, showing methods and algorithms to construct a polynomial in R which satisfies the above Hermite-type interpolation problem and its relative Lagrange-type version. [ABSTRACT FROM AUTHOR]

Reed-Solomon (RS) codes are used in many storage systems for failure recovery. In popular software implementations, RS codes are defined by using a parity check matrix that is either a Cauchy matrix padded with an identity or a Vandermonde matrix. The encoding complexity can be reduced by searching for a Cauchy matrix that has a smaller number of ‘1's in its bit matrices or exploiting Reed-Muller (RM) transform in the Vandermonde matrix multiplication. This article proposes two new approaches that improve upon the previous schemes. In our first approach, different constructions of finite fields are explored to further reduce the number of ‘1's in the bit matrices of the Cauchy matrix and a new searching method is developed to find the matrices with minimum number of ‘1's. Our second approach defines RS codes using a parity check matrix in the format of a Vandermonde matrix concatenated with an identity matrix so that the multiplication with the inverse erasure columns in the encoding is eliminated and the decoding can be carried out using simplified formulas. The Vandermonde matrix in such an unconventional RS code definition needs to be constructed using finite field elements in non-consecutive order. A modification is also developed in this article to enable the application of the RM transform in this case to reduce the matrix multiplication complexity. For 4-erasure-correcting RS codes over $GF(2^8)$ G F (2 8) , the two proposed approaches increase the encoding throughput by 40 and 15 percent on average over the prior works based on Cauchy matrix and Vandermonde matrix with RM transform, respectively, for a range of codeword length. Moreover, the decoding throughput is also significantly improved. [ABSTRACT FROM AUTHOR]

We investigate interconnected aspects of hyperderivatives of polynomials over finite fields, q -th powers of polynomials, and specializations of Vandermonde matrices. We construct formulas for Carlitz multiplication coefficients using hyperderivatives and symmetric polynomials, and we prove identities for hyperderivative power sums in terms of specializations of the inverse of the Vandermonde matrix. As an application of these results we give a new proof of a theorem of Thakur on explicit formulas for Anderson's special polynomials for log-algebraicity on the Carlitz module. Furthermore, by combining results of Pellarin and Perkins with these techniques, we obtain a new proof of Anderson's theorem in the general case. [ABSTRACT FROM AUTHOR]

In this paper, we first present a sufficient and necessary condition for a Vandermonde matrix over tropical algebra to be determinant balanced. Then we provide a formula of the principal eigenvalue of a Vandermonde matrix. Finally, we present a version of polynomial interpolation for tropical algebra. [ABSTRACT FROM AUTHOR]

We study the equivalence between the ring learning with errors and polynomial learning with errors problems for cyclotomic number fields, namely: we prove that both problems are equivalent via a polynomial noise increase as long as the number of distinct primes dividing the conductor is kept constant. We refine our bound in the case where the conductor is divisible by at most three primes and we give an asymptotic subexponential formula for the condition number of the attached Vandermonde matrix valid for arbitrary degree. [ABSTRACT FROM AUTHOR]

Recursive MDS matrices are used for the design of linear diffusion layers in lightweight cryptographic applications. Most of the works on the construction of recursive MDS matrices either consider matrices over finite fields or block matrices over G L (m , F 2). In the first case, there have been works on the direct construction of recursive MDS matrices. The latter case is hard to deal with because of its non-commutative nature. There has not been any serious attempt to look for recursive MDS matrices over finite commutative rings, in particular over local rings of even characteristic. In this work, we present several methods for the construction of recursive MDS companion matrices over finite commutative rings. The main tools are the simple expressions for the determinant of (generalized) Vandermonde and linearized matrices. We show that the determinant of a linearized matrix over a finite commutative ring of prime characteristic can be expressed in a simple form. We discuss a technique called subring construction with which MDS matrices over product rings can be constructed using MDS matrices over subrings. We give a few examples of recursive MDS companion matrices over local rings of even characteristic. We also discuss some results on the nonexistence of recursive MDS matrices over certain rings for some parameter choices. [ABSTRACT FROM AUTHOR]