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.     

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.     

Complexity of some natural problems on the class of computable I-algebras

We study computable Boolean algebras with distinguished ideals (I-algebras for short). We prove that the isomorphism problem for computable I-algebras is Σ ₁ ¹ -complete and show that the computable isomorphism problem and the computable categoricity problem for computable I-algebras are Σ ₃ ⁰ -complete.     

Introduction to the Special Issue on Discrete Event Models of Continuous Systems

Automatic control systems rely on models to predict the near future and identification algorithms to adapt the models to changing process behaviour. The traditionally highly complex models of the activated sludge process developed for scientific purposes cannot be identified from on-line measurements and are not suited for process control purposes in their present form. Model decoupling based on the different time scales of the dynamic processes is one possible way of attacking this problem. It allows the implementation of more simple and realistically applicable controllers in combination with predictions based on simplified models in hierarchical control structure. This paper discusses these concepts and presents a reduced order model describing carbonaceous removal, nitrification, and denitrification in a medium time scale (several hours/days). The model parameters are identifiable from available on-line measurements and the dynamic behaviour is verified against computer simulations of the IAWQ activated sludge model no. 1.     

Inducing regulation of any digraphs

For a given structure D (digraph, multidigraph, or pseudodigraph) and an integer r large enough, a smallest inducing r-regularization of D is constructed. This regularization is an r-regular superstructure of the smallest possible order with bounded arc multiplicity, and containing D as an induced substructure. The sharp upper bound on the number, ρ, of necessary new vertices among such superstructures for n-vertex general digraphs D is determined, ρ being called the inducing regulation number of D. For being the maximum among semi-degrees in D, simple n-vertex digraphs D with largest possible ρ are characterized if either or (where the case is not a trivial subcase of ).     

Polynomial reduction of time-space scheduling to time scheduling

We study the University Course Timetabling Problem (UCTP). In particular we deal with the following question: is it possible to decompose UCTP into two problems, namely, (i) a time scheduling, and (ii) a space scheduling. We have arguments that it is not possible. Therefore we study UCTP with the assumption that each room belongs to exactly one type of room. A type of room is a set of rooms, which have similar properties. We prove that in this case UCTP is polynomially reducible to time scheduling. Hence we solve UCTP with the following method: at first we solve time scheduling and subsequently we solve space scheduling with a polynomial O(n³) algorithm. In this way we obtain a radical (exponential) speed-up of algorithms for UCTP. The method was applied at P.J. Šafárik University.