We use submultiplicative companion matrix norms to provide new bounds for roots for a given polynomial <i>P</i>(<i>X</i>) over the field C[<i>X</i>]. From a <i>n</i>...We use submultiplicative companion matrix norms to provide new bounds for roots for a given polynomial <i>P</i>(<i>X</i>) over the field C[<i>X</i>]. From a <i>n</i>×<i>n</i> Fiedler companion matrix <i>C</i>, sparse companion matrices and triangular Hessenberg matrices are introduced. Then, we identify a special triangular Hessenberg matrix <i>L<sub>r</sub></i>, supposed to provide a good estimation of the roots. By application of Gershgorin’s theorems to this special matrix in case of submultiplicative matrix norms, some estimations of bounds for roots are made. The obtained bounds have been compared to known ones from the literature precisely Cauchy’s bounds, Montel’s bounds and Carmichel-Mason’s bounds. According to the starting formel of <i>L<sub>r</sub></i>, we see that the more we have coefficients closed to zero with a norm less than 1, the more the Sparse method is useful.展开更多
In this paper, we first show that a generic m×n Fiedler matrix may have 2m-n-1 kinds of factorizations which are very complicated when m is much larger than n. In this work, two special cases are examined, one is...In this paper, we first show that a generic m×n Fiedler matrix may have 2m-n-1 kinds of factorizations which are very complicated when m is much larger than n. In this work, two special cases are examined, one is an m×n Fiedler matrix being factored as a product of (m - n) Fiedler matrices, the other is an m×(m - 2) Fiedler matrix's factorization. Then we discuss the relation among the numbers of parameters of three generic m×n, n×p and m×p Fiedler matrices, and obtain some useful results.展开更多
The concept of Fiedler matrices was introduced in [1] by L. Stuart and R.Weaver.In[1], they investigated the factorization of Fiedler matrix into Fiedler matrices and pre-sented some open questions i. e. When is a Fie...The concept of Fiedler matrices was introduced in [1] by L. Stuart and R.Weaver.In[1], they investigated the factorization of Fiedler matrix into Fiedler matrices and pre-sented some open questions i. e. When is a Fiedler matrix factorizable as a product ofFiedler matrices? Are there useful sufficient conditions? If a Fiedler matrix is factorizable,are the factors unique? If not, are the dimensions of the factors unique? In this paper,展开更多
In this paper, we develop a cascadic multigrid algorithm for fast computation of the Fiedler vector of a graph Laplacian, namely, the eigenvector corresponding to the second smallest eigenvalne. This vector has been f...In this paper, we develop a cascadic multigrid algorithm for fast computation of the Fiedler vector of a graph Laplacian, namely, the eigenvector corresponding to the second smallest eigenvalne. This vector has been found to have applications in fields such as graph partitioning and graph drawing. The algorithm is a purely algebraic approach based on a heavy edge coarsening scheme and pointwise smoothing for refinement. To gain theoretical insight, we also consider the related cascadic multigrid method in the geometric setting for elliptic eigenvalue problems and show its uniform convergence under certain assumptions. Numerical tests are presented for computing the Fiedler vector of several practical graphs, and numerical results show the efficiency and optimality of our proposed cascadic multigrid algorithm.展开更多
文摘We use submultiplicative companion matrix norms to provide new bounds for roots for a given polynomial <i>P</i>(<i>X</i>) over the field C[<i>X</i>]. From a <i>n</i>×<i>n</i> Fiedler companion matrix <i>C</i>, sparse companion matrices and triangular Hessenberg matrices are introduced. Then, we identify a special triangular Hessenberg matrix <i>L<sub>r</sub></i>, supposed to provide a good estimation of the roots. By application of Gershgorin’s theorems to this special matrix in case of submultiplicative matrix norms, some estimations of bounds for roots are made. The obtained bounds have been compared to known ones from the literature precisely Cauchy’s bounds, Montel’s bounds and Carmichel-Mason’s bounds. According to the starting formel of <i>L<sub>r</sub></i>, we see that the more we have coefficients closed to zero with a norm less than 1, the more the Sparse method is useful.
基金This paper is supported by the National Nature Science Foundation, China （No. 60475017）.
文摘In this paper, we first show that a generic m×n Fiedler matrix may have 2m-n-1 kinds of factorizations which are very complicated when m is much larger than n. In this work, two special cases are examined, one is an m×n Fiedler matrix being factored as a product of (m - n) Fiedler matrices, the other is an m×(m - 2) Fiedler matrix's factorization. Then we discuss the relation among the numbers of parameters of three generic m×n, n×p and m×p Fiedler matrices, and obtain some useful results.
基金This work is supported by the Natural Scientific Research Foundation of Yunnan Province(200A0001--1M)the Scientific Research Foundation of Education Commission of Yunnan Province(9911126)
文摘The concept of Fiedler matrices was introduced in [1] by L. Stuart and R.Weaver.In[1], they investigated the factorization of Fiedler matrix into Fiedler matrices and pre-sented some open questions i. e. When is a Fiedler matrix factorizable as a product ofFiedler matrices? Are there useful sufficient conditions? If a Fiedler matrix is factorizable,are the factors unique? If not, are the dimensions of the factors unique? In this paper,
文摘In this paper, we develop a cascadic multigrid algorithm for fast computation of the Fiedler vector of a graph Laplacian, namely, the eigenvector corresponding to the second smallest eigenvalne. This vector has been found to have applications in fields such as graph partitioning and graph drawing. The algorithm is a purely algebraic approach based on a heavy edge coarsening scheme and pointwise smoothing for refinement. To gain theoretical insight, we also consider the related cascadic multigrid method in the geometric setting for elliptic eigenvalue problems and show its uniform convergence under certain assumptions. Numerical tests are presented for computing the Fiedler vector of several practical graphs, and numerical results show the efficiency and optimality of our proposed cascadic multigrid algorithm.
基金Supported by Natural Science Foundation of Department of Education of Anhui Province and the Projectof Anhui University for Talents Gruop Construction.
