65F50 Sparse matrices
A new implicitly-restarted Krylov subspace method
for real symmetric/skew-symmetric generalized eigenvalue problems
is presented. The new method improves and generalizes the SHIRA method
to the case where the skew symmetric matrix is singular.
It computes a few eigenvalues and eigenvectors of the matrix pencil
close to a given target point. Several applications from control theory are
presented and the properties of the new method are illustrated by benchmark
examples.
A new concept is introduced for the adaptive finite element discretization of partial differential equations that have a sparsely
representable solution. Motivated by recent work on compressed sensing, a recursive mesh refinement procedure is presented that uses linear programming to find a good approximation to the sparse solution on a given refinement level. Then only those parts of the mesh are refined that belong to nonzero expansion coefficients. Error estimates for this procedure are refined and the behavior of the procedure is demonstrated via some simple elliptic model problems.
Here we analyze algebraic multilevel methods applied to non-symmetric M-matrices.
We consider two types of multilevel approximate block factorizations.
The first one is related to the AMLI method.
The second method
is the multiplicative counterpart of the AMLI approach which we call
multiplicative algebraic multilevel method, the MAMLI method. The MAMLI method is closely related to certain geometric
and algebraic multigrid methods like the AMGr method. Although these
multilevel methods work very well
in practice for many problems, there is not that much known about
theoretical convergence
properties for non-symmetric problems.
Here, we establish
convergence results and comparison results between AMLI and MAMLI
multilevel methods
applied to non-symmetric M-matrices.
We establish theoretical comparison results for algebraic multi-level
methods applied
to nonsingular non-symmetric M-matrices.
We consider two types of multi-level approximate block factorizations or AMG methods, the
AMLI and the MAMLI method.
We compare
the spectral radii
of the iteration matrices of these methods. This comparison
shows, that the spectral radius of the MAMLI method is less than or equal to
the spectral radius of the AMLI method.
Moreover, we establish how the quality of the approximations
in the block factorization effects the spectral radii of the
iteration
matrices. We prove comparisons results
for different approximation of the fine grid block as well as for the
used Schur
complement. We also establish a theoretical comparison between the
AMG methods and the classical block Jacobi and block Gauss-Seidel methods.
Three properties of matrices: the spark, the mutual incoherence and the restricted isometry property have recently been introduced in the context of compressed sensing. We study these properties for matrices that are Kronecker products and show how these properties relate to those of the factors. For the mutual incoherence we also
discuss results for sums of Kronecker products.