Tsung-Ming HuangDepartment of Mathematics, National Taiwan Normal UniversityTiexiang LiSchool of Mathematics, Southeast UniversityWei-De LiDepartment of Mathematics, National Tsing-Hua UniversityJia-Wei LinDepartment of Applied Mathematics, National Chiao Tung UniversityWen-Wei LinDepartment of Applied Mathematics, National Chiao Tung UniversityTian HengDepartment of Applied Mathematics, National Chiao Tung University
Numerical Analysis and Scientific ComputingNumerical Linear Algebramathscidoc:1810.07001
Calculation of band structures of three dimensional photonic crystals amounts to solving large-scale Maxwell eigenvalue problems, which are notoriously challenging due to high multiplicity of zero eigenvalues. In this paper, we try to address this problem in such a broad context that band structures of three dimensional isotropic photonic crystals in all $14$ Bravais lattices can be efficiently computed in a unified framework. In this work, we uncover the delicate machinery behind several key results of our framework and on the basis of this new understanding we drastically simplify the derivations, proofs and arguments. Particular effort is made on reformulating the Bloch condition for all $14$ Bravais lattices in the redefined orthogonal coordinate system, and establishing eigen-decomposition of discrete partial derivative operators by identifying the hierarchical structure of the underlying normal (block) companion matrix, and reducing the eigen-decomposition of the double-curl operator to a simple factorization of a $3$-by-$3$ complex skew-symmetric matrix. With the validity of the novel nullspace free method in the broad context, we perform some calculations on one benchmark system to demonstrate the accuracy and efficiency of our algorithm to solve Maxwell eigenvalue problems.
The doubling algorithms are very efficient iterative methods for computing the unique minimal nonnegative solution to an M-matrix algebraic Riccati equation (MARE). They are globally and quadratically convergent, except for MARE in the critical case where convergence is linear with the linear rate 1/2. However, the initialization phase and the doubling iteration kernel of any doubling algorithm involve inverting nonsingular M-matrices. In particular, for MARE in the critical case, the M-matrices in
the doubling iteration kernel, although nonsingular, move towards singular M-matrices at convergence. These inversions are causes of concerns on entrywise relative accuracy of the eventually computed minimal nonnegative solution. Fortunately, a nonsingular M-matrix can be inverted by the GTH-like algorithm of Alfa, Xue, and Ye [Math. Comp., 71:217--236, 2002] to almost full entrywise relative accuracy, provided a triplet representation of the matrix is known. Recently, Nguyen and Poloni [Numer. Math., 130(4):763--792, 2015] discovered a way to construct triplet representations in a cancellation-free manner for all involved M-matrices in the doubling iteration kernel, for a special class of MAREs arising from Markov-modulated fluid queues. In this paper, we extend Nguyen's and Poloni's work to all MAREs by also devising a way to construct the triplet representations cancellation-free. Our construction, however, is not a straightforward extension of theirs. It is made possible by
an introduction of novel recursively computable auxiliary nonnegative vectors. As the second contribution, we propose an entrywise relative residual for an approximate solution. The residual has an appealing feature of being able to reveal the entrywise relative accuracies of all entries, large and small, of the approximation. This is in marked contrast to the usual legacy normalized residual which reflects relative accuracies of large entries well but not so much those of very tiny entries. Numerical examples are presented to demonstrate and confirm our claims.
The Lanczos method is often used to solve a large scale symmetric matrix eigenvalue problem. It is well-known that the single-vector Lanczos method can only find one copy of any multiple eigenvalue and encounters slow convergence towards clustered eigenvalues. On the other hand, the block Lanczos method can compute all or some of the copies of a multiple eigenvalue and, with a suitable block size, also compute clustered eigenvalues much faster. The existing convergence theory due to Saad for the block Lanczos method, however, does not fully reflect this phenomenon since the theory was established to bound approximation errors in each individual approximate eigenpairs. Here, it is argued that in the presence of an eigenvalue cluster,
the entire approximate eigenspace associated with the cluster should be considered as a whole, instead of each individual approximate eigenvectors, and likewise for approximating clusters of eigenvalues. In this paper, we obtain error bounds on approximating eigenspaces and eigenvalue clusters. Our bounds are much sharper than the existing ones and expose true rates of convergence of the block Lanczos method towards eigenvalue clusters. Furthermore, their sharpness is independent of
the closeness of eigenvalues within a cluster. Numerical examples are presented to support our claims.
Li-Ping ZhangDepartment of Mathematical Sciences, Tsinghua UniversityLiqun QiDepartment of Applied Mathematics, Hong Kong Polytechnic UniversityGuanglu ZhouDepartment of Mathematics and Statistics, Curtin University, Perth, Australia
Numerical Linear Algebramathscidoc:1804.26001
SIAM Journal on Matrix Analysis and Applications, 35, (2), 437-452, 2014.4
We introduceM-tensors. This concept extends the concept ofM-matrices. We denote
Z-tensors as the tensors with nonpositive off-diagonal entries. We show that M-tensors must be Ztensors
and the maximal diagonal entry must be nonnegative. The diagonal elements of a symmetric
M-tensor must be nonnegative. A symmetric M-tensor is copositive. Based on the spectral theory
of nonnegative tensors, we show that the minimal value of the real parts of all eigenvalues of an Mtensor
is its smallest H+-eigenvalue and also is its smallest H-eigenvalue. We show that a Z-tensor is
an M-tensor if and only if all its H+-eigenvalues are nonnegative. Some further spectral properties of
M-tensors are given. We also introduce strong M-tensors, and some corresponding conclusions are
given. In particular, we show that all H-eigenvalues of strong M-tensors are positive. We apply this
property to study the positive definiteness of a class of multivariate forms associated with Z-tensors.
We also propose an algorithm for testing the positive definiteness of such a multivariate form.
Manifold parameterizations have been applied to various fields of commercial industries. Several efficient algorithms for the computation of triangular surface mesh parameterizations have been proposed in recent years. However, the computation of tetrahedral volumetric mesh parameterizations is more challenging due to the fact that the number of mesh points would become enormously large when the higher resolution mesh is considered and the bijectivity of parameterizations is more difficult to guarantee. In this paper, we develop a novel volumetric stretch energy minimization algorithm for volume-preserving parameterizations of simply connected 3-manifolds with a single boundary under the restriction that the boundary is a spherical area-preserving mapping. In addition, our algorithm can also be applied to compute spherical angle- and area-preserving parameterizations of genus-zero closed surfaces, respectively. Several numerical experiments indicate that the developed algorithms are more efficient and reliable compared to other existing algorithms. Numerical results on applications of the manifold partition and the mesh processing for three-dimensional printing are demonstrated thereafter to show the robustness of the proposed algorithm.
So-Hsiang ChouBowling Green State UniversityTsung-Ming HuangNational Taiwan Normal UniversityTiexiang LiSoutheast UniversityJia-Wei LinNational Chiao Tung UniversityWen-Wei LinNational Chiao Tung University
Numerical Linear Algebramathscidoc:1802.26001
Journal of Computational Physics, 386, 611-631, 2019.6
The standard Yee's scheme for the Maxwell eigenvalue problems places the discrete electric field variable at the midpoints of the edges of the grid cells. It performs well when the permittivity is a scalar field. However, when the permittivity is a Hermitian full tensor filed it would generate un-physical complex eigenvalues or frequencies. In this paper, we propose a finite element method which can be interpreted as a modified Yee's scheme to overcome this difficulty. This interpretation enables us to create a fast FFT eigensolver that can compute very effectively the band structure of the anisotropic photonic crystal with SC and FCC lattices. Furthermore, we overcome the usual
large null space associated with the Maxwell eigenvalue problem by deriving a null-space free discrete eigenvalue problem which involves a crucial Hermitian positive definite linear system to be solved in each of the iteration steps. It is demonstrated that the CG method without preconditioning converges in 37 iterations even when the dimension of the matrix is as large as $5,184,000$.
We give the formulation of a Riemannian Newton algorithm for solving a class of nonlinear eigenvalue problems by minimizing a total energy function subject to the orthogonality constraint. Under some mild assumptions, we establish the global and quadratic convergence of the proposed method. Moreover, the positive definiteness condition of the Riemannian Hessian of the total energy function at a solution is derived. Some numerical tests are reported to illustrate the efficiency of the proposed method for solving large-scale problems.
In this paper, we focus on the stochastic inverse eigenvalue problem of reconstructing a stochastic matrix from the prescribed spectrum. We directly reformulate the stochastic inverse eigenvalue problem as a constrained optimization problem over several matrix manifolds to minimize the distance between isospectral matrices and stochastic matrices. Then we propose a geometric Polak–Ribi`ere–Polyak-based nonlinear conjugate gradient method for solving the constrained optimization problem. The global convergence of the proposed method is established. Our method can also be extended to the stochastic inverse eigenvalue problem with prescribed entries. An extra advantage is that our models yield new isospectral flow methods. Finally, we report some numerical tests to illustrate the efficiency of the proposed method for solving the stochastic inverse eigenvalue problem and the case of prescribed entries.
We propose an inverse iterative method for computing the Perron pair of an irreducible nonnegative
third order tensor.
The method involves the selection of a
parameter $\theta_k$ in the $k$th iteration.
For every positive starting vector, the method converges quadratically
and is positivity preserving in the sense that the vectors approximating the Perron vector are strictly positive in each iteration.
It is also shown that $\theta_k=1$ near convergence.
The computational work for each iteration of the proposed method
is less than four times (three times if the tensor is symmetric in modes two and three, and twice if we also take the parameter to be $1$ directly)
that for each iteration of the Ng--Qi--Zhou algorithm, which is linearly convergent
for essentially positive tensors.