Página 1 dos resultados de 25 itens digitais encontrados em 0.013 segundos

Parameter Reconstruction of Vibration Systems from Partial Eigeninformation

Dong, Bo; Lin, Matthew M.; Chu, Moody T.
Fonte: PubMed Publicador: PubMed
Tipo: Artigo de Revista Científica
EN
Relevância na Pesquisa
25.95%
Quadratic matrix polynomials are fundamental to vibration analysis. Because of the predetermined interconnectivity among the constituent elements and the mandatory nonnegativity of the physical parameters, most given vibration systems will impose some inherent structure on the coefficients of the corresponding quadratic matrix polynomials. In the inverse problem of reconstructing a vibration system from its observed or desirable dynamical behavior, respecting the intrinsic structure becomes important and challenging both theoretically and practically. The issue of whether a structured inverse eigenvalue problem is solvable is problem dependent and has to be addressed structure by structure. In an earlier work, physical systems that can be modeled under the paradigm of a serially linked mass-spring system have been considered via specifically formulated inequality systems. In this paper, the framework is generalized to arbitrary generally linked systems. In particular, given any configuration of interconnectivity in a mass-spring system, this paper presents a mechanism that systematically and automatically generates a corresponding inequality system. A numerical approach is proposed to determine whether the inverse problem is solvable and...

Using implicit equations of parametric curves and surfaces without computing them: Polynomial algebra by values

Diaz Toca, Gema María; Fioravanti Villanueva, Mario; González Vega, Laureano; Shakoori, Azar
Fonte: Elsevier Publicador: Elsevier
Tipo: info:eu-repo/semantics/article; acceptedVersion
ENG
Relevância na Pesquisa
25.83%
The availability of the implicit equation of a plane curve or of a 3D surface can be very useful in order to solve many geometric problems involving the considered curve or surface: for example, when dealing with the point position problem or answering intersection questions. On the other hand, it is well known that in most cases, even for moderate degrees, the implicit equation is either difficult to compute or, if computed, the high degree and the big size of the coefficients makes extremely difficult its use in practice. We will show that, for several problems involving plane curves, 3D surfaces and some of their constructions (for example, offsets), it is possible to use the implicit equation (or, more precisely, its properties) without needing to explicitly determine it. We replace the computation of the implicit equation with the evaluation of the considered parameterizations in a set of points. We then translate the geometric problem in hand, into one or several generalized eigenvalue problems on matrix pencils (depending again on several evaluations of the considered parameterizations). This is the so-called “polynomial algebra by values” approach where the huge polynomial equations coming from Elimination Theory (e.g....

Two variable orthogonal polynomials and structured matrices

Delgado, Antonia M.; Geronimo, Jeffrey S.; Iliev, Plamen; Marcellán, Francisco
Fonte: Society for Industrial and Applied Mathematics (SIAM) Publicador: Society for Industrial and Applied Mathematics (SIAM)
Tipo: Artigo de Revista Científica Formato: application/pdf
Publicado em //2006 ENG
Relevância na Pesquisa
36.01%
We consider bivariate real valued polynomials orthogonal with respect to a positive linear functional. The lexicographical and reverse lexicographical orderings are used to order the monomials. Recurrence formulas are derived between polynomials of different degrees. These formulas link the orthogonal polynomials constructed using the lexicographical ordering with those constructed using the reverse lexicographical ordering. Relations between the coefficients in the recurrence formulas are established and used to give necessary and sufficient conditions for the existence of a positive linear functional. Links to the theory of matrix orthogonal polynomials are developed as well the consequences of a zero assumption on one of the coefficients in the the recurrence formulas.; The second and fourth authors were partially supported by NATO grant PST.CLG.979738. The second author was partially supported by an NSF grant. The first and fourth authors were partially supported by grant BFM2003-06335-C03-02 from the Dirección General de Investigación, Ministerio de Educación y Ciencia of Spain.; 30 pages, no figures.-- MSC2000 codes: 42C05, 30E05, 47A57.; MR#: MR2218946 (2006m:47021); Zbl#: Zbl 1136.42305

Fiedler matrices: numerical and structural properties

Pérez Álvaro, Javier
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: Tese de Doutorado
ENG
Relevância na Pesquisa
35.95%
The first and second Frobenius companion matrices appear frequently in numerical application, but it is well known that they possess many properties that are undesirable numerically, which limit their use in applications. Fiedler companion matrices, or Fiedler matrices for brevity, introduced in 2003, is a family of matrices which includes the two Frobenius matrices. The main goal of this work is to study whether or not Fiedler companion matrices can be used with more reliability than the Frobenius ones in the numerical applications where Frobenius matrices are used. For this reason, in this work we present a thorough study of Fiedler matrices: their structure and numerical properties, where we mean by numerical properties those properties that are interesting for applying these matrices in numerical computations, and some of their applications in the field on numerical linear algebra. The introduction of Fiedler companion matrices is an example of a simple idea that has been very influential in the development of several lines of research in the numerical linear algebra field. This family of matrices has important connections with a number of topics of current interest, including: polynomial root finding algorithms, linearizations of matrix polynomials...

Blumenthal's theorem for Laurent orthogonal polynomials

Ranga, A. S.; Van Assche, W.
Fonte: Elsevier B.V. Publicador: Elsevier B.V.
Tipo: Artigo de Revista Científica Formato: 255-278
ENG
Relevância na Pesquisa
26.01%
We investigate polynomials satisfying a three-term recurrence relation of the form B-n(x) = (x - beta(n))beta(n-1)(x) - alpha(n)xB(n-2)(x), with positive recurrence coefficients alpha(n+1),beta(n) (n = 1, 2,...). We show that the zeros are eigenvalues of a structured Hessenberg matrix and give the left and right eigenvectors of this matrix, from which we deduce Laurent orthogonality and the Gaussian quadrature formula. We analyse in more detail the case where alpha(n) --> alpha and beta(n) --> beta and show that the zeros of beta(n) are dense on an interval and that the support of the Laurent orthogonality measure is equal to this interval and a set which is at most denumerable with accumulation points (if any) at the endpoints of the interval. This result is the Laurent version of Blumenthal's theorem for orthogonal polynomials. (C) 2002 Elsevier B.V. (USA).

Spectral equivalence of matrix polynomials and the Index Sum Theorem

Terán Vergara, Fernando de; Martínez Dopico, Froilan C.; Mackey, Don Steven
Fonte: Elsevier Publicador: Elsevier
Tipo: info:eu-repo/semantics/acceptedVersion; info:eu-repo/semantics/article
Publicado em /10/2014 ENG
Relevância na Pesquisa
46.07%
This research was partially supported by Ministerio de Ciencia e Innovación of Spain through grant MTM-2009-09281, and by Ministerio de Economía y Competitividad of Spain through grant MTM2012-32542.

Large vector spaces of block-symmetric strong linearizations of matrix polynomials

Bueno, M. I.; Martínez Dopico, Froilan C.; Furtado, S.; Rychnovsky, M.
Fonte: Elsevier Publicador: Elsevier
Tipo: info:eu-repo/semantics/acceptedVersion; info:eu-repo/semantics/article
Publicado em 15/07/2015 ENG
Relevância na Pesquisa
66.07%
Given a matrix polynomial P(lambda) = Sigma(k)(i=0) lambda(i) A(i) of degree k, where A(i) are n x n matrices with entries in a field F, the development of linearizations of P(lambda) that preserve whatever structure P(lambda) might posses has been a very active area of research in the last decade. Most of the structure-preserving linearizations of P(lambda) discovered so far are based on certain modifications of block-symmetric linearizations. The block-symmetric linearizations of P(lambda) available in the literature fall essentially into two classes: linearizations based on the so-called Fiedler pencils with repetition, which form a finite family, and a vector space of dimension k of block-symmetric pencils, called DL(P), such that most of its pencils are linearizations. One drawback of the pencils in DL(P) is that none of them is a linearization when P(lambda) is singular. In this paper we introduce new vector spaces of block,symmetric pencils, most of which are strong linearizations of P(lambda). The dimensions of these spaces are O(n(2)), which, for n >= root k, are much larger than the dimension of DL(P). When k is odd, many of these vector spaces contain linearizations also when P(lambda) is singular. The coefficients of the block-symmetric pencils in these new spaces can be easily constructed as k x k block-matrices whose n x n blocks are of the form 0...

Backward stability of polynomial root-finding using Fiedler companion matrices

Terán Vergara, Fernando de; Martínez Dopico, Froilan C.; Pérez, J.
Fonte: Oxford University Press Publicador: Oxford University Press
Tipo: info:eu-repo/semantics/acceptedVersion; info:eu-repo/semantics/article; info:eu-repo/semantics/conferenceObject
Publicado em 08/09/2014 ENG
Relevância na Pesquisa
25.95%
Computing roots of scalar polynomials as the eigenvalues of Frobenius companion matrices using backward stable eigenvalue algorithms is a classical approach. The introduction of new families of companion matrices allows for the use of other matrices in the root-finding problem. In this paper, we analyze the backward stability of polynomial root-finding algorithms via Fiedler companion matrices. In other words, given a polynomial p(z), the question is to determine whether the whole set of computed eigenvalues of the companion matrix, obtained with a backward stable algorithm for the standard eigenvalue problem, are the set of roots of a nearby polynomial or not. We show that, if the coefficients of p(z) are bounded in absolute value by a moderate number, then algorithms for polynomial root-finding using Fiedler matrices are backward stable, and Fiedler matrices are as good as the Frobenius companion matrices. This allows us to use Fiedler companion matrices with favorable structures in the polynomial root-finding problem. However, when some of the coefficients of the polynomial are large, Fiedler companion matrices may produce larger backward errors than Frobenius companion matrices, although in this case neither Frobenius nor Fiedler matrices lead to backward stable computations. To prove this we obtain explicit expressions for the change...

Correlations of RMT Characteristic Polynomials and Integrability: Hermitean Matrices

Osipov, Vladimir Al.; Kanzieper, Eugene
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
25.93%
Integrable theory is formulated for correlation functions of characteristic polynomials associated with invariant non-Gaussian ensembles of Hermitean random matrices. By embedding the correlation functions of interest into a more general theory of tau-functions, we (i) identify a zoo of hierarchical relations satisfied by tau-functions in an abstract infinite-dimensional space, and (ii) present a technology to translate these relations into hierarchically structured nonlinear differential equations describing the correlation functions of characteristic polynomials in the physical, spectral space. Implications of this formalism for fermionic, bosonic, and supersymmetric variations of zero-dimensional replica field theories are discussed at length. A particular emphasis is placed on the phenomenon of fermionic-bosonic factorisation of random-matrix-theory correlation functions.; Comment: 62 pages, 1 table, published version (typos corrected)

Solving polynomial eigenvalue problems by means of the Ehrlich-Aberth method

Bini, Dario A.; Noferini, V.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 26/07/2012
Relevância na Pesquisa
25.87%
Given the $n\times n$ matrix polynomial $P(x)=\sum_{i=0}^kP_i x^i$, we consider the associated polynomial eigenvalue problem. This problem, viewed in terms of computing the roots of the scalar polynomial $\det P(x)$, is treated in polynomial form rather than in matrix form by means of the Ehrlich-Aberth iteration. The main computational issues are discussed, namely, the choice of the starting approximations needed to start the Ehrlich-Aberth iteration, the computation of the Newton correction, the halting criterion, and the treatment of eigenvalues at infinity. We arrive at an effective implementation which provides more accurate approximations to the eigenvalues with respect to the methods based on the QZ algorithm. The case of polynomials having special structures, like palindromic, Hamiltonian, symplectic, etc., where the eigenvalues have special symmetries in the complex plane, is considered. A general way to adapt the Ehrlich-Aberth iteration to structured matrix polynomial is introduced. Numerical experiments which confirm the effectiveness of this approach are reported.; Comment: Submitted to Linear Algebra Appl

On backward errors of structured polynomial eigenproblems solved by structure preserving linearizations

Adhikari, Bibhas; Alam, Rafikul
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 15/07/2009
Relevância na Pesquisa
46.36%
First, we derive explicit computable expressions of structured backward errors of approximate eigenelements of structured matrix polynomials including symmetric, skew-symmetric, Hermitian, skew-Hermitian, even and odd polynomials. We also determine minimal structured perturbations for which approximate eigenelements are exact eigenelements of the perturbed polynomials. Next, we analyze the effect of structure preserving linearizations of structured matrix polynomials on the structured backward errors of approximate eigenelements. We identify structure preserving linearizations which have almost no adverse effect on the structured backward errors of approximate eigenelements of the polynomials. Finally, we analyze structured pseudospectra of a structured matrix polynomial and establish a partial equality between unstructured and structured pseudospectra.; Comment: 27 pages, submitted

Nearly Optimal Computations with Structured Matrices

Pan, Victor Y.; Tsigaridas, Elias
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 18/04/2014
Relevância na Pesquisa
25.94%
We estimate the Boolean complexity of multiplication of structured matrices by a vector and the solution of nonsingular linear systems of equations with these matrices. We study four basic most popular classes, that is, Toeplitz, Hankel, Cauchy and Van-der-monde matrices, for which the cited computational problems are equivalent to the task of polynomial multiplication and division and polynomial and rational multipoint evaluation and interpolation. The Boolean cost estimates for the latter problems have been obtained by Kirrinnis in \cite{kirrinnis-joc-1998}, except for rational interpolation, which we supply now. All known Boolean cost estimates for these problems rely on using Kronecker product. This implies the $d$-fold precision increase for the $d$-th degree output, but we avoid such an increase by relying on distinct techniques based on employing FFT. Furthermore we simplify the analysis and make it more transparent by combining the representation of our tasks and algorithms in terms of both structured matrices and polynomials and rational functions. This also enables further extensions of our estimates to cover Trummer's important problem and computations with the popular classes of structured matrices that generalize the four cited basic matrix classes.; Comment: (2014-04-10)

Borcea's variance conjectures on the critical points of polynomials

Khavinson, Dmitry; Pereira, Rajesh; Putinar, Mihai; Saff, Edward B.; Shimorin, Serguei
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
25.87%
Closely following recent ideas of J. Borcea, we discuss various modifications and relaxations of Sendov's conjecture about the location of critical points of a polynomial with complex coefficients. The resulting open problems are formulated in terms of matrix theory, mathematical statistics or potential theory. Quite a few links between classical works in the geometry of polynomials and recent advances in the location of spectra of small rank perturbations of structured matrices are established. A couple of simple examples provide natural and sometimes sharp bounds for the proposed conjectures.

Linearizations for Rosenbrock system polynomials and rational matrix functions

Alam, Rafikul; Behera, Namita
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/05/2015
Relevância na Pesquisa
25.9%
Our aim in this paper is two-fold: First, for computing zeros of a linear time-invariant (LTI) system $\Sigma$ in {\em state-space form}, we introduce a "trimmed structured linearization", which we refer to as {\em Rosenbrock linearization}, of the Rosenbrock system polynomial $\mathcal{S}(\lam)$ associated with $\Sigma.$ We also introduce Fiedler-like matrices for $\mathcal{S}(\lam)$ and describe constructions of Fiedler-like pencils for $\mathcal{S}(\lam).$ We show that the Fiedler-like pencils of $\mathcal{S}(\lam)$ are Rosenbrock linearizations of the system polynomial $\mathcal{S}(\lam).$ Second, with a view to developing a direct method for solving rational eigenproblems, we introduce "linearization" of a rational matrix function. We describe a state-space framework for converting a rational matrix function $G(\lam)$ to an "equivalent" matrix pencil $\mathbb{L}(\lam)$ of smallest dimension such that $G(\lam)$ and $\mathbb{L}(\lam)$ have the same "eigenstructure" and we refer to such a pencil $\mathbb{L}(\lam)$ as a "linearization" of $G(\lam).$ Indeed, by treating $G(\lam)$ as the transfer function of an LTI system $\Sigma_G$ in state-space form via state-space realization, we show that the Fiedler-like pencils of the Rosenbrock system polynomial associated with $\Sigma_G$ are "linearizations" of $G(\lam)$ when the system $\Sigma_G$ is both controllable and observable.; Comment: 28 pages

Backward errors and linearizations for palindromic matrix polynomials

Adhikari, Bibhas
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.19%
We derive computable expressions of structured backward errors of approximate eigenelements of *-palindromic and *-anti-palindromic matrix polynomials. We also characterize minimal structured perturbations such that approximate eigenelements are exact eigenelements of the perturbed polynomials. We detect structure preserving linearizations which have almost no adverse effect on the structured backward errors of approximate eigenelements of the *-palindromic and *-anti-palindromic polynomials.; Comment: 19 pages, submitted

Interactive certificate for the verification of Wiedemann's Krylov sequence: application to the certification of the determinant, the minimal and the characteristic polynomials of sparse matrices

Dumas, Jean-Guillaume; Kaltofen, Erich; Thomé, Emmanuel
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 04/07/2015
Relevância na Pesquisa
26.11%
Certificates to a linear algebra computation are additional data structures for each output, which can be used by a-possibly randomized- verification algorithm that proves the correctness of each output. Wiede-mann's algorithm projects the Krylov sequence obtained by repeatedly multiplying a vector by a matrix to obtain a linearly recurrent sequence. The minimal polynomial of this sequence divides the minimal polynomial of the matrix. For instance, if the $n\times n$ input matrix is sparse with n 1+o(1) non-zero entries, the computation of the sequence is quadratic in the dimension of the matrix while the computation of the minimal polynomial is n 1+o(1), once that projected Krylov sequence is obtained. In this paper we give algorithms that compute certificates for the Krylov sequence of sparse or structured $n\times n$ matrices over an abstract field, whose Monte Carlo verification complexity can be made essentially linear. As an application this gives certificates for the determinant, the minimal and characteristic polynomials of sparse or structured matrices at the same cost.

Permanents of Circulants: a Transfer Matrix Approach (Expanded Version)

Golin, Mordecai J.; Leung, Yiu Cho; Wang, Yajun
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 07/08/2007
Relevância na Pesquisa
25.9%
Calculating the permanent of a (0,1) matrix is a #P-complete problem but there are some classes of structured matrices for which the permanent is calculable in polynomial time. The most well-known example is the fixed-jump (0,1) circulant matrix which, using algebraic techniques, was shown by Minc to satisfy a constant-coefficient fixed-order recurrence relation. In this note we show how, by interpreting the problem as calculating the number of cycle-covers in a directed circulant graph, it is straightforward to reprove Minc's result using combinatorial methods. This is a two step process: the first step is to show that the cycle-covers of directed circulant graphs can be evaluated using a transfer matrix argument. The second is to show that the associated transfer matrices, while very large, actually have much smaller characteristic polynomials than would a-priori be expected. An important consequence of this new viewpoint is that, in combination with a new recursive decomposition of circulant-graphs, it permits extending Minc's result to calculating the permanent of the much larger class of circulant matrices with non-fixed (but linear) jumps. It also permits us to count other types of structures in circulant graphs, e.g., Hamiltonian Cycles.; Comment: 33 pages...

Gr\"obner Bases of Bihomogeneous Ideals generated by Polynomials of Bidegree (1,1): Algorithms and Complexity

Faugère, Jean-Charles; Din, Mohab Safey El; Spaenlehauer, Pierre-Jean
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
25.93%
Solving multihomogeneous systems, as a wide range of structured algebraic systems occurring frequently in practical problems, is of first importance. Experimentally, solving these systems with Gr\"obner bases algorithms seems to be easier than solving homogeneous systems of the same degree. Nevertheless, the reasons of this behaviour are not clear. In this paper, we focus on bilinear systems (i.e. bihomogeneous systems where all equations have bidegree (1,1)). Our goal is to provide a theoretical explanation of the aforementionned experimental behaviour and to propose new techniques to speed up the Gr\"obner basis computations by using the multihomogeneous structure of those systems. The contributions are theoretical and practical. First, we adapt the classical F5 criterion to avoid reductions to zero which occur when the input is a set of bilinear polynomials. We also prove an explicit form of the Hilbert series of bihomogeneous ideals generated by generic bilinear polynomials and give a new upper bound on the degree of regularity of generic affine bilinear systems. This leads to new complexity bounds for solving bilinear systems. We propose also a variant of the F5 Algorithm dedicated to multihomogeneous systems which exploits a structural property of the Macaulay matrix which occurs on such inputs. Experimental results show that this variant requires less time and memory than the classical homogeneous F5 Algorithm.; Comment: 31 pages

Contractive determinantal representations of stable polynomials on a matrix polyball

Grinshpan, Anatolii; Kaliuzhnyi-Verbovetskyi, Dmitry S.; Vinnikov, Victor; Woerdeman, Hugo J.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 20/03/2015
Relevância na Pesquisa
25.9%
We show that an irreducible polynomial $p$ with no zeros on the closure of a matrix unit polyball, a.k.a. a cartesian product of Cartan domains of type I, and such that $p(0)=1$, admits a strictly contractive determinantal representation, i.e., $p=\det(I-KZ_n)$, where $n=(n_1,...,n_k)$ is a $k$-tuple of nonnegative integers, $Z_n=\bigoplus_{r=1}^k(Z^{(r)}\otimes I_{n_r})$, $Z^{(r)}=[z^{(r)}_{ij}]$ are complex matrices, $p$ is a polynomial in the matrix entries $z^{(r)}_{ij}$, and $K$ is a strictly contractive matrix. This result is obtained via a noncommutative lifting and a theorem on the singularities of minimal noncommutative structured system realizations.

The Ehrlich-Aberth method for palindromic matrix polynomials represented in the Dickson basis

Gemignani, Luca; Noferini, Vanni
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/11/2011
Relevância na Pesquisa
35.83%
An algorithm based on the Ehrlich-Aberth root-finding method is presented for the computation of the eigenvalues of a T-palindromic matrix polynomial. A structured linearization of the polynomial represented in the Dickson basis is introduced in order to exploit the symmetry of the roots by halving the total number of the required approximations. The rank structure properties of the linearization allow the design of a fast and numerically robust implementation of the root-finding iteration. Numerical experiments that confirm the effectiveness and the robustness of the approach are provided.; Comment: in press in Linear Algebra Appl. (2011)