Conditions of LU as M, H-matrix

ＣｏｎｄｉｔｉｏｎｓｏｆＬＵａｓＭ，Ｈ－ｍａｔｒｉｘ￥ＷａｎｇＨｕａ；ＬｉＱｉｎｇ（ＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇＩｎｓｔｉｔｕｔｅｏｆＰＬＡ）（ＣｏｌｌｅｇｅｏｆＥｎｇｉｎｅｅｒｉｎｇＹａｎｂｉａｎＵｎｉｖｅｒｓｉｔｙ）ＷａｎｇＣｈｕ...     

圈平方图复杂性的一个简捷证明

本文给出了圈平方图支撑树数目公式的一个简捷证明。从而也获得它的渐近性质．     

Polynomial algorithms for m × (m + 1) integer programs and m × (m + k) diophantine systems

Recent results of Kannan and Bachem (on computing the Smith Normal Form of a matrix) and Lenstra (on solving integer inequality systems) are used with classical results by Smith to obtain polynomial-time algorithms for solving m × (m + 1) equality constrained integer programs and m × (m + k) systems of diophantine equations for fixed k.     

Computation of differential operators in aggregated wavelet frame coordinates

Manuel Werner ^{Adaptive wavelet algorithms for solving operator equations havebeen shown to converge with the best possible rates in linearcomplexity. For the latter statement, all costs are taken intoaccount, i.e. also the cost of approximating entries from theinfinite stiffness matrix with respect to the wavelet basisusing suitable quadrature. A difficulty is the constructionof a suitable wavelet basis on the generally non-trivially shapeddomain on which the equation is posed. In view of this, recentlycorresponding algorithms have been proposed that require onlya wavelet frame instead of a basis. By employing an overlappingdecomposition of the domain, where each subdomain is the smoothparametric image of the unit cube, and by lifting a waveletbasis on this cube to each of the subdomains, the union of thesecollections defines such a frame. A potential bottleneck withinthis approach is the efficient approximation of entries correspondingto pairs of wavelets from different collections. Indeed, suchwavelets are piecewise smooth with respect to mutually non-nestedpartitions. In this paper, considering partial differentialoperators and spline wavelets on the subdomains, we proposean easy implementable quadrature scheme to approximate the requiredentries, which allows the fully discrete adaptive frame algorithmto converge with the optimal rate in linear complexity.}     

Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs

Multicut is a fundamental network communication and connectivity problem. It is defined as: given an undirected graph and a collection of pairs of terminal vertices, find a minimum set of edges or vertices whose removal disconnects each pair. We mainly focus on the case of removing vertices, where we distinguish between allowing or disallowing the removal of terminal vertices. Complementing and refining previous results from the literature, we provide several NP-completeness and (fixed-parameter) tractability results for restricted classes of graphs such as trees, interval graphs, and graphs of bounded treewidth.     

The unitary completion and QR iterations for a class of structured matrices

We consider the problem of completion of a matrix with a specified lower triangular part to a unitary matrix. In this paper we obtain the necessary and sufficient conditions of existence of a unitary completion without any additional constraints and give a general formula for this completion. The paper is mainly focused on matrices with the specified lower triangular part of a special form. For such a specified part the unitary completion is a structured matrix, and we derive in this paper the formulas for its structure. Next we apply the unitary completion method to the solution of the eigenvalue problem for a class of structured matrices via structured QR iterations.

     

Visibility maps of segments and triangles in 3D

Let T be a set of n triangles in three-dimensional space, let s be a line segment, and let t be a triangle, both disjoint from T. We consider the subdivision of T based on (in)visibility from s; this is the visibility map of the segment s with respect to T. The visibility map of the triangle t is defined analogously. We look at two different notions of visibility: strong (complete) visibility, and weak (partial) visibility. The trivial Ω(n²) lower bound for the combinatorial complexity of the strong visibility map of both s and t is almost tight: we prove an O(n²(n)) upper bound for both structures, where (n) is the extremely slowly increasing inverse Ackermann function. Furthermore, we prove that the weak visibility map of s has complexity Θ(n⁵), and the weak visibility map of t has complexity Θ(n⁷). If T is a polyhedral terrain, the complexity of the weak visibility map is Ω(n⁴) and O(n⁵), both for a segment and a triangle. We also present efficient algorithms to compute all discussed structures.     

The complexity of detecting fixed-density clusters

We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let γ:N→Q₊ be any density function, i.e., γ is computable in polynomial time and satisfies γ(k)?k-1 for all k∈N. Then γ-CLUSTER is the problem of deciding, given an undirected graph G and a natural number k, whether there is a subgraph of G on k vertices that has average degree at least γ(k). For γ(k)=k-1, this problem is the same as the well-known CLIQUE problem, and thus NP-complete. In contrast to this, the problem is known to be solvable in polynomial time for γ(k)=2. We ask for the possible functions γ such that γ-CLUSTER remains NP-complete or becomes solvable in polynomial time. We show a rather sharp boundary: γ CLUSTER is NP-complete if γ=2+Ω(1/k^1-ε) for some ε>0 and has a polynomial-time algorithm for γ=2+O(1/k). The algorithm also shows that for γ=2+O(1/k^1-o(1)), γ-CLUSTER is solvable in subexponential time 2^no(1).     

An inverse model for the most uniform problem

In this paper, we consider a kind of inverse model for the most uniform problem. This model has some practical background. It is shown that the model can be solved in polynomial time whenever an associated min-sum problem can be solved in polynomial time.     

Out-of-band quasiseparable matrices

We study structured matrices which consist of a band part and quasiseparable parts below and upper the band. We extend algorithms known for quasiseparable matrices, i.e. for the case when the band consists of the main diagonal only, to a wider class of matrices. The matrices which we consider may be treated as an usual quasiseparable matrices with larger orders of generators. Hence one can apply the methods developed for usual quasiseparable matrices and obtain various linear complexity O(N) algorithms. However in this case the coefficients in N in the complexity estimates turns out to be quite large. In this paper we use the structure more accurately by division of the matrix into three parts in which the middle part is the band instead of diagonal as it is used for usual quasiseparable matrices. This approach allows to use better the structure of the matrix in order to improve the coefficients in N in the complexity estimates for the algorithms. This method works for algorithms which keep invariant the structure.