WySR RSS Feed

Subscribe to WySR RSS Feed feed
Recent documents in Wyoming Scholars Repository
Updated: 11 hours 41 min ago

Discontinuity Propagation in Delay Differential-Algebraic Equations

Sun, 2018-12-09 19:22

The propagation of primary discontinuities in initial value problems for linear delay differential-algebraic equations (DDAEs) is discussed. Based on the (quasi-) Weierstra{\ss} form for regular matrix pencils, a complete characterization of the different propagation types is given and algebraic criteria in terms of the matrices are developed. The analysis, which is based on the method of steps, takes into account all possible inhomogeneities and history functions and thus serves as a worst-case scenario. Moreover, it reveals possible hidden delays in the DDAE and allows to study exponential stability of the DDAE based on the spectral abscissa. The new classification for DDAEs is compared to existing approaches in the literature and the impact of splicing conditions on the classification is studied.

Asymptotic results on the condition number of FD matrices approximating semi-elliptic PDEs

Sun, 2018-12-09 19:22

This work studies the asymptotic behavior of the spectral condition number of the matrices $A_{nn}$ arising from the discretization of semi-elliptic partial differential equations of the form \bdm -\left( a(x,y)u_{xx}+b(x,y)u_{yy}\right)=f(x,y), \edm on the square $\Omega=(0,1)^2,$ with Dirichlet boundary conditions, where the smooth enough variable coefficients $a(x,y), b(x,y)$ are nonnegative functions on $\overline{\Omega}$ with zeros. In the case of coefficient functions with a single and common zero, it is discovered that apart from the minimum order of the zero also the direction that it occurs is of great importance for the characterization of the growth of the condition number of $A_{nn}$. On the contrary, when the coefficient functions have non intersecting zeros, it is proved that independently of the order their zeros, and their positions, the condition number of $A_{nn}$ behaves asymptotically exactly as in the case of strictly elliptic differential equations, i.e., it grows asymptotically as $n^2$. Finally, the more complicated case of coefficient functions having curves of roots is considered, and conjectures for future work are given. In conclusion, several experiments are presented that numerically confirm the developed theoretical analysis.

REGULARITY RADIUS: PROPERTIES, APPROXIMATION AND A NOT A PRIORI EXPONENTIAL ALGORITHM

Thu, 2018-12-06 02:30

The radius of regularity, sometimes spelled as the radius of nonsingularity, is a measure providing the distance of a given matrix to the nearest singular one. Despite its possible application strength this measure is still far from being handled in an efficient way also due to findings of Poljak and Rohn providing proof that checking this property is NP-hard for a general matrix. There are basically two approaches to handle this situation. Firstly, approximation algorithms are applied and secondly, tighter bounds for radius of regularity are considered. Improvements of both approaches have been recently shown by Hartman and Hlad\'{i}k (doi:10.1007/978-3-319-31769-4\_9) utilizing relaxation of the radius computation to semidefinite programming. An estimation of the regularity radius using any of the above mentioned approaches is usually applied to general matrices considering none or just weak assumptions about the original matrix. Surprisingly less explored area is represented by utilization of properties of special classes of matrices as well as utilization of classical algorithms extended to be used to compute the considered radius. This work explores a process of regularity radius analysis and identifies useful properties enabling easier estimation of the corresponding radius values. At first, checking finiteness of this characteristic is shown to be a polynomial problem along with determining a sharp upper bound on the number of nonzero elements of the matrix to obtain infinite radius. Further, relationship between maximum (Chebyshev) norm and spectral norm is used to construct new bounds for the radius of regularity. Considering situations where the known bounds are not tight enough, a new method based on Jansson-Rohn algorithm for testing regularity of an interval matrix is presented which is not a priory exponential along with numerical experiments. For a situation where an input matrix has a special form, several corresponding results are provided such as exact formulas for several special classes of matrices, e.g., for totally positive and inverse non-negative, or approximation algorithms, e.g., rank-one radius matrices. For tridiagonal matrices, an algorithm by Bar-On, Codenotti and Leoncini is utilized to design a polynomial algorithm to compute the radius of regularity.

Commutators Involving Matrix Functions

Fri, 2018-11-30 10:32

Some results are obtained for matrix commutators involving matrix exponentials $\left(\left[e^{A},B\right],\left[e^{A},e^{B}\right]\right)$ and their norms.

Determinants of Interval Matrices

Mon, 2018-11-19 08:16

In this paper we shed more light on determinants of real interval matrices. Computing the exact bounds on a determinant of an interval matrix is an NP-hard problem. Therefore, attention is first paid to approximations. NP-hardness of both relative and absolute approximation is proved. Next, methods computing verified enclosures of interval determinants and their possible combination with preconditioning are discussed. A new method based on Cramer's rule was designed. It returns similar results to the state-of-the-art method, however, it is less consuming regarding computational time. Other methods transferable from real matrices (e.g., the Gerschgorin circles, Hadamard's inequality) are discussed. New results about classes of interval matrices with polynomially computable tasks related to determinant are proved (symmetric positive definite matrices, class of matrices with identity midpoint matrix, tridiagonal H-matrices). The mentioned methods were compared for random general and symmetric matrices.

Inequalities between $\mid A\mid + \mid B\mid $ and $\mid A^{*} \mid + \mid B^{*} \mid$

Sat, 2018-11-17 02:14

Let $A$ and $B$ be complex square matrices. Some inequalities between $\mid A \mid + \mid B \mid$ and $\mid A^{*} \mid + \mid B^{*} \mid$ are established. Applications of these inequalities are also given. For example, in the Frobenius norm, $$ \parallel\, A+B \,\parallel_{F} \leq \sqrt[4]{2} \parallel \mid A\mid + \mid B\mid \, \parallel_{F}. $$

Structured eigenvalue/eigenvector backward errors of matrix pencils arising in optimal control

Sat, 2018-11-17 02:14

Eigenvalue and eigenpair backward errors are computed for matrix pencils arising in optimal control. In particular, formulas for backward errors are developed that are obtained under block-structure-preserving and symmetry-structure-preserving perturbations. It is shown that these eigenvalue and eigenpair backward errors are sometimes significantly larger than the corresponding backward errors that are obtained under perturbations that ignore the special structure of the pencil.

Perturbation results and the forward order law for the Moore-Penrose inverse of a product

Wed, 2018-11-14 20:57

New expressions are given for the Moore-Penrose inverse of a product $AB$ of two complex matrices. Furthermore, an expression for $(AB)\dg - B\dg A\dg$ for the case where $A$ or $B$ is of full rank is provided. Necessary and sufficient conditions for the forward order law for the Moore-Penrose inverse of a product to hold are established. The perturbation results presented in this paper are applied to characterize some mixed-typed reverse order laws for the Moore-Penrose inverse, as well as the reverse order law.

Convergence of a modified Newton method for a matrix polynomial equation arising in stochastic problem

Mon, 2018-11-12 23:01

The Newton iteration is considered for a matrix polynomial equation which arises in stochastic problem. In this paper, it is shown that the elementwise minimal nonnegative solution of the matrix polynomial equation can be obtained using Newton's method if the equation satisfies the sufficient condition, and the convergence rate of the iteration is quadratic if the solution is simple. Moreover, it is shown that the convergence rate is at least linear if the solution is non-simple, but a modified Newton method whose iteration number is less than the pure Newton iteration number can be applied. Finally, numerical experiments are given to compare the effectiveness of the modified Newton method and the standard Newton method.

Estimators Comparison of Separable Covariance Structure with One Component as Compound Symmetry Matrix

Mon, 2018-11-05 17:57

The maximum likelihood estimation (MLE) of separable covariance structure with one component as compound symmetry matrix has been widely studied in the literature. Nevertheless, the proposed estimates are not given in explicit form and can be determined only numerically. In this paper we give an alternative form of MLE and we show that this new algorithm is much quicker than the algorithms given in the literature.\\ Another estimator of covariance structure can be found by minimizing the entropy loss function. In this paper we give three methods of finding the best approximation of separable covariance structure with one component as compound symmetry matrix and we compare the quickness of proposed algorithms.\\ We conduct simulation studies to compare statistical properties of MLEs and entropy loss estimators (ELEs), such us biasedness, variability and loss. Another estimator of covariance structure can be found by minimizing the entropy loss function. In this paper we give three methods of finding the best approximation of separable covariance structure with one component as compound symmetry matrix and we compare the quickness of proposed algorithms. We conduct simulation studies to compare statistical properties of MLEs and entropy loss estimators (ELEs), such us biasedness and variability.

On Projection of a Positive Definite Matrix on a Cone of Nonnegative Definite Toeplitz Matrices

Fri, 2018-10-12 14:20

We consider approximation of a given positive definite matrix by nonnegative definite banded Toeplitz matrices. We show that the projection on linear space of Toeplitz matrices does not always preserve nonnegative definiteness. Therefore we characterize a convex cone of nonnegative definite banded Toeplitz matrices which depends on the matrix dimensions, and we show that the condition of positive definiteness given by Parter [{\em Numer. Math. 4}, 293--295, 1962] characterizes the asymptotic cone. In this paper we give methodology and numerical algorithm of the projection basing on the properties of a cone of nonnegative definite Toeplitz matrices. This problem can be applied in statistics, for example in the estimation of unknown covariance structures under the multi-level multivariate models, where positive definiteness is required. We conduct simulation studies to compare statistical properties of the estimators obtained by projection on the cone with a given matrix dimension and on the asymptotic cone.

Explicit Block-Structures for Block-Symmetric Fiedler-like pencils

Tue, 2018-10-09 17:18

In the last decade, there has been a continued effort to produce families of strong linearizations of a matrix polynomial $P(\lambda)$, regular and singular, with good properties, such as, being companion forms, allowing the recovery of eigenvectors of a regular $P(\lambda)$ in an easy way, allowing the computation of the minimal indices of a singular $P(\lambda)$ in an easy way, etc. As a consequence of this research, families such as the family of Fiedler pencils, the family of generalized Fiedler pencils (GFP), the family of Fiedler pencils with repetition, and the family of generalized Fiedler pencils with repetition (GFPR) were constructed. In particular, one of the goals was to find in these families structured linearizations of structured matrix polynomials. For example, if a matrix polynomial $P(\lambda)$ is symmetric (Hermitian), it is convenient to use linearizations of $P(\lambda)$ that are also symmetric (Hermitian). Both the family of GFP and the family of GFPR contain block-symmetric linearizations of $P(\lambda)$, which are symmetric (Hermitian) when $P(\lambda)$ is. Now the objective is to determine which of those structured linearizations have the best numerical properties. The main obstacle for this study is the fact that these pencils are defined implicitly as products of so-called elementary matrices. Recent papers in the literature had as a goal to provide an explicit block-structure for the pencils belonging to the family of Fiedler pencils and any of its further generalizations to solve this problem. In particular, it was shown that all GFP and GFPR, after permuting some block-rows and block-columns, belong to the family of extended block Kronecker pencils, which are defined explicitly in terms of their block-structure. Unfortunately, those permutations that transform a GFP or a GFPR into an extended block Kronecker pencil do not preserve the block-symmetric structure. Thus, in this paper, the family of block-minimal bases pencils, which is closely related to the family of extended block Kronecker pencils, and whose pencils are also defined in terms of their block-structure, is considered as a source of canonical forms for block-symmetric pencils. More precisely, four families of block-symmetric pencils which, under some generic nonsingularity conditions are block minimal bases pencils and strong linearizations of a matrix polynomial, are presented. It is shown that the block-symmetric GFP and GFPR, after some row and column permutations, belong to the union of these four families. Furthermore, it is shown that, when $P(\lambda)$ is a complex matrix polynomial, any block-symmetric GFP and GFPR is permutationally congruent to a pencil in some of these four families. Hence, these four families of pencils provide an alternative but explicit approach to the block-symmetric Fiedler-like pencils existing in the literature.

The Largest Distance (Signless Laplacian) Eigenvalue and Maximum Row Sum of Non-transmission-regular Graphs

Tue, 2018-10-09 17:18

Let $G=(V(G),E(G))$ be a $k$-connected graph with $n$ vertices and $m$ edges. Let $D(G)$ be the distance matrix of $G$. Suppose $\lambda_1(D)\geq \cdots \geq \lambda_n(D)$ are the $D$-eigenvalues of $G$. The transmission of $v_i \in V(G)$, denoted by $Tr_G(v_i)$ is defined to be the sum of distances from $v_i$ to all other vertices of $G$, i.e., the row sum $D_{i}(G)$ of $D(G)$ indexed by vertex $v_i$ and suppose that $D_1(G)\geq \cdots \geq D_n(G)$. The $Wiener~ index$ of $G$ denoted by $W(G)$ is given by $W(G)=\frac{1}{2}\sum_{i=1}^{n}D_i(G)$. Let $Tr(G)$ be the $n\times n$ diagonal matrix with its $(i,i)$-entry equal to $TrG(v_i)$. The distance signless Laplacian matrix of $G$ is defined as $D^Q(G)=Tr(G)+D(G)$ and its spectral radius is denoted by $\rho_1(D^Q(G))$ or $\rho_1$. A connected graph $G$ is said to be $t$-transmission-regular if $Tr_G(v_i) =t$ for every vertex $v_i\in V(G)$, otherwise, non-transmission-regular. In this paper, we respectively estimate $D_1(G)-\lambda_1(G)$ and $2D_1(G)-\rho_1(G)$ for a $k$-connected non-transmission-regular graph in different ways and compare these obtained results. And we conjecture that $D_1(G)-\lambda_1(G)>\frac{1}{n+1}$. Moreover, we show that the conjecture is valid for trees.

Positive and Z-operators on Closed Convex Cones

Sun, 2018-10-07 22:44

Let $K$ be a closed convex cone with dual $\dual{K}$ in a finite-dimensional real Hilbert space. A \emph{positive operator} on $K$ is a linear operator $L$ such that $L\of{K} \subseteq K$. Positive operators generalize the nonnegative matrices and are essential to the Perron-Frobenius theory. It is said that $L$ is a \emph{\textbf{Z}-operator} on $K$ if % \begin{equation*} \ip{L\of{x}}{s} \le 0 \;\text{ for all } \pair{x}{s} \in \cartprod{K}{\dual{K}} \text{ such that } \ip{x}{s} = 0. \end{equation*} % The \textbf{Z}-operators are generalizations of \textbf{Z}-matrices (whose off-diagonal elements are nonpositive) and they arise in dynamical systems, economics, game theory, and elsewhere. In this paper, the positive and \textbf{Z}-operators are connected. This extends the work of Schneider, Vidyasagar, and Tam on proper cones, and reveals some interesting similarities between the two families.

Spectral Bounds for the Connectivity of Regular Graphs with Given Order

Sun, 2018-10-07 22:44

The second-largest eigenvalue and second-smallest Laplacian eigenvalue of a graph are measures of its connectivity. These eigenvalues can be used to analyze the robustness, resilience, and synchronizability of networks, and are related to connectivity attributes such as the vertex- and edge-connectivity, isoperimetric number, and characteristic path length. In this paper, two upper bounds are presented for the second-largest eigenvalues of regular graphs and multigraphs of a given order which guarantee a desired vertex- or edge-connectivity. The given bounds are in terms of the order and degree of the graphs, and hold with equality for infinite families of graphs. These results answer a question of Mohar.

Bounded linear operators that preserve the weak supermajorization on $\ell^1(I)^+$

Sun, 2018-10-07 22:44

Linear preservers of weak supermajorization which is defined on positive functions contained in the discrete Lebesgue space $\ell^1(I)$ are characterized. Two different classes of operators that preserve the weak supermajorization are formed. It is shown that every linear preserver may be decomposed as sum of two operators from the above classes, and conversely, the sum of two operators which satisfy an additional condition is a linear preserver. Necessary and sufficient conditions under which a bounded linear operator is a linear preserver of the weak supermajorization are given. It is concluded that positive linear preservers of the weak supermajorization coincide with preservers of weak majorization and standard majorization on $\ell^1(I)$.

BOUNDS ON THE SUM OF MINIMUM SEMIDEFINITE RANK OF A GRAPH AND ITS COMPLEMENT

Wed, 2018-09-26 09:55

The minimum semi-definite rank (msr) of a graph is the minimum rank among all positive semi-definite matrices associated to the graph. The graph complement conjecture gives an upper bound for the sum of the msr of a graph and the msr of its complement. It is shown that when the msr of a graph is equal to its independence number, the graph complement conjecture holds with a better upper bound. Several sufficient conditions are provided for the msr of different classes of graphs to equal to its independence number.

Identifying combinatorially symmetric Hidden Markov Models

Thu, 2018-08-23 18:51

A sufficient criterion for the unique parameter identification of combinatorially symmetric Hidden Markov Models, based on the structure of their transition matrix, is provided. If the observed states of the chain form a zero forcing set of the graph of the Markov model, then it is uniquely identifiable and an explicit reconstruction method is given.

The Largest Eigenvalue and Some Hamiltonian Properties of Graphs

Thu, 2018-08-23 18:51

In this note, sufficient conditions, based on the largest eigenvalue, are presented for some Hamiltonian properties of graphs.

Positive solutions of the system of operator equations $A_1X=C_1,XA_2=C_2, A_3XA^*_3=C_3, A_4XA^*_4=C_4$ in Hilbert $C^*$-modules

Thu, 2018-08-23 18:51

Necessary and sufficient conditions are given for the operator system $A_1X=C_1$, $XA_2=C_2$, $A_3XA^*_3=C_3$, and $A_4XA^*_4=C_4$ to have a common positive solution, where $A_i$'s and $C_i$'s are adjointable operators on Hilbert $C^*$-modules. This corrects a published result by removing some gaps in its proof. Finally, a technical example is given to show that the proposed investigation in the setting of Hilbert $C^*$-modules is different from that of Hilbert spaces.

Pages