Bimatroidal independence systems

An independence system Σ=(X, F) is called bimatroidal if there exist two matroidsM=(X F _M) andN=(X, F _N) such thatF=F _M∪ F_N. When this is the case, {M,N} is called a bimatroidal decomposition of Σ. This paper initiates the study of bimatroidal systems. Given the collection of circuits of an arbitrary independence system Σ (or, equivalently, the constraints of a set-covering problem), we address the following question: does Σ admit a bimatroidal decomposition {M,N} and, if so, how can we actually produce the circuits ofM andN? We derive a number of results concerning this problem, and we present a polynomial time algorithm to solve it when every two circuits of Σ have at most one common element. We also propose different polynomial time algorithms for set covering problems defined on the circuit-set of bimatroidal systems.     

Rank-axiomatic characterizations of independence systems

Motivated by the rank-axiomatic definitions of a matroid and Woodall's characterization of independence systems [6] we provide an abstract framework for general independence systems in terms of their rank function.     

Smoothing algorithms for nonlinear finite-dimensional systems

Systems are considered where the state evolves either as a diffusion process or as a finitestate Markov process, and the measurement process consists either of a nonlinear function of the state with additive white noise or as a counting process with intensity dependent on the state. Fixed interval smooting is considered, and the first main result obtained expresses a smoothing probability or a probability density symmetrically in terms of forward filtered, reverse-time filterd and unfiltered quantities; an associated result replaces the unfiltered and reverse-time filtered qauantities by a likelihood function. Then stochastic differential equationsare obtained for the evolution of the reverse-time filtered probability or probability density and the reverse-time likelihood function. Lastly, a partial differential equation is obtained linking smoothed and forward filterd probabilities or probability densities; in all instances considered, this equation is not driven by any measurement process. The different approaches are also linked to known techniques applicable in the linear-Gaussian case.     

Volume-preserving algorithms for source-free dynamical systems

Summary. In this paper, we first expound why the volume-preserving algorithms are proper for numerically solving source-free systems and then prove all the conventional methods are not volume-preserving. Secondly, we give a general method of constructing volume-preserving difference schemes for source-free systems on the basis of decomposing a source-free vector field as a finite sum of essentially 2-dimensional Hamiltonian fields and of composing the corresponding essentially symplectic schemes into a volume-preserving one. Lastly, we make some special discussions for so-called separable source-free systems for which arbitrarily high order explicit revertible volume-preserving schemes can be constructed. Received March 22, 1994 / Revised version received January 25, 1995     

GMDH algorithms for complex systems modelling

At present, GMDH algorithms give us a way to identify and forecast economic processes in the case of noised and short input sampling. In contrast to neural networks, the results are explicit mathematical models, obtained in a relatively short time. For ill-defined objects with very big noises, better results are obtained by analog complexing methods. Nets with active neurons should be applied to increase accuracy. Active neurons are able, during the self-organizing process, to estimate which inputs are necessary to minimize the given objective function of the neuron. In the neuronet with such neurons, we have a twofold multilayered structure: neurons themselves are multilayered, and they will be united into a multilayered network.

SelfOrganize! is an easy-to-use modelling tool which realizes twice-multilayered neu-ronets and enables the creation of time series, single input/single output, multi-input/single output and multi-input/multi-output systems (system of equations). Successful applications are shown in the field of analysis and prediction of characteristics of stock markets in financial risk control modelling.     

Some inversion algorithms for discrete systems

Several algorithms are proposed to solve the inversion problem in the presence of information about the system state or the system output under certain additional assumptions (the wave model of the unknown input is assumed known). The problem of estimation from the output is solved by constructing state observers for a system of arbitrary relative order. Necessary conditions for the applicability of the proposed algorithms are identified. Error bounds of the approximation algorithms are estimated. __________ Translated from Nelineinaya Dinamika i Upravlenie, No. 4, pp. 119–126, 2004.     

On a classification of independence systems

By generalizing matroid axiomatics we provide a framework in which independence systems may be classified. The concept is applied to independence systems arising from well-known combinatorial optimization problems such ask-matroid-intersection-, matchoid-, vertex packingor travelling salesman-problems.     

On a classification of independence systems

By generalizing matroid axiomatics we provide a framework in which independence systems may be classified. The concept is applied to independence systems arising from well known combinatorial optimization problems such as k-matroid intersection, matchoid, vertex packing in finite graphs and travelling salesman problems.     

Transpose-free Lanczos-type algorithms for nonsymmetric linear systems

The method of Lanczos for solving systems of linear equations is implemented by using recurrence relationships between formal orthogonal polynomials. A drawback is that the computation of the coefficients of these recurrence relationships usually requires the use of the transpose of the matrix of the system. Due to the indirect addressing, this is a costly operation. In this paper, a new procedure for computing these coefficients is proposed. It is based on the recursive computation of the products of polynomials appearing in their expressions and it does not involve the transpose of the matrix. Moreover, our approach allows to implement simultaneously and at a low price a Lanczos-type product method such as the CGS or the BiCGSTAB. This revised version was published online in June 2006 with corrections to the Cover Date.     

Robust inversion algorithms for vector linear systems

We consider the inversion problem for linear systems, which involves estimation of the unknown input vector. The inversion problem is considered for a system with a vector output and a vector input assuming that the observed output is of higher dimension than the unknown input. The problem is solved by using a controlled model in which the control stabilizes the deviations of the model output from the system output. The stabilizing model control or its averaged form may be used as the estimate of the unknown system input. __________ Translated from Nelineinaya Dinamika i Upravlenie, No. 4, pp. 17–22, 2004.     

Fast algorithms for high-order spline collocation systems

Summary. In this paper, we present a complete eigenvalue analysis for arbitrary order -spline collocation methods applied to the Poisson equation on a rectangular domain with Dirichlet boundary conditions. Based on this analysis, we develop some fast algorithms for solving a class of high-order spline collocation systems which arise from discretizing the Poisson equation. Received April 8, 1997 / Revised version received August 29, 1997     

New look-ahead Lanczos-type algorithms for linear systems

Summary. A breakdown (due to a division by zero) can arise in the algorithms for implementing Lanczos' method because of the non-existence of some formal orthogonal polynomials or because the recurrence relationship used is not appropriate. Such a breakdown can be avoided by jumping over the polynomials involved. This strategy was already used in some algorithms such as the MRZ and its variants. In this paper, we propose new implementations of the recurrence relations of these algorithms which only need the storage of a fixed number of vectors, independent of the length of the jump. These new algorithms are based on Horner's rule and on a different way for computing the coefficients of the recurrence relationships. Moreover, these new algorithms seem to be more stable than the old ones and they provide better numerical results. Numerical examples and comparisons with other algorithms will be given. Received September 2, 1997 / Revised version received July 24, 1998     

Recursive algorithms for unbalanced banded Toeplitz systems

Direct recursive algorithms for the solution of band Toeplitz systems are considered here. They exploit the displacement rank properties, which allow a large reduction of computational efforts and storage requirements. Their use of the Sherman–Morrison–Woodbury formula turns out to be particularly suitable for the case of unbalanced bandwidths. The computational costs of the algorithms under consideration are compared both in a theoretical and practical setting. Some stability issues are discussed as well. Copyright © 2009 John Wiley & Sons, Ltd.     

Ordering algorithms for irreducible sparse linear systems

Ordinary algorithms aim to pre-order a matrix in order to achieve a favourable structure for factorization. Two prototype structures are described which are commonly aimed at by current algorithms. A different structure, based on a lower Hessenberg form, is introduced. We show that the common structures may be obtained from the Hessenberg form in a simple way. A fundamental and very simple algorithm is presented for deriving the lower Hessenberg form. This algorithm is inherently a part of other common algorithms, but is usually obscured by other detailed heuristics. Some of these heuristics are seen to correspond to different tie-break rules in the fundamental algorithm. We describe a particularly simple tie-break rule used in SPK1 [11], which is effective and not at all well known. Ordinary algorithms need to be modified to enable pivoting for numerical stability to be carried out. We describe how the idea of threshold pivoting can be used in the context of these algorithms. Most ordering algorithms in common use employ some sort of look-ahead to promote a favourable structure. It is argued that look-ahead is generally ineffective in practice, and that numerical evidence supports the use of very simple strategies. A new ordering algorithm is presented which aims to obtain a narrower bandwidth in the lower Hessenberg form. Some limited numerical experience is presented which enables us to draw tentative conclusions about various ordering strategies, and how they compare with those in common use.     

Practical Quasi-Newton algorithms for singular nonlinear systems

Quasi-Newton methods for solving singular systems of nonlinear equations are considered in this paper. Singular roots cause a number of problems in implementation of iterative methods and in general deteriorate the rate of convergence. We propose two modifications of QN methods based on Newton’s and Shamanski’s method for singular problems. The proposed algorithms belong to the class of two-step iterations. Influence of iterative rule for matrix updates and the choice of parameters that keep iterative sequence within convergence region are empirically analyzed and some conclusions are obtained.     

Parallel algorithms for solving large linear systems

The solution of linear systems continues to play an important role in scientific computing. The problems to be solved often are of very large size, so that solving them requires large computer resources. To solve these problems, at least supercomputers with large shared memory or massive parallel computer systems with distributed memory are needed.

This paper gives a survey of research on parallel implementation of various direct methods to solve dense linear systems. In particular are considered: Gaussian elimination, Gauss-Jordan elimination and a variant due to Huard (1979), and an algorithm due to Enright (1978), designed in relation to solving (stiff) ODEs, such that stepsize and other method parameters can easily be varied.

Some theoretical results are mentioned, including a new result on error analysis of Huard's algorithm. Moreover, practical considerations and results of experiments on supercomputers and on a distributed-memory computer system are presented.     

On the geometric structure of independence systems

A bouquet of matroids is a combinatorial structure that generalizes the properties of matroids. Given an independence system, there exist several bouquets of matroids having the same family of independent sets. We show that the collection of these geometries forms in general a meet semi-lattice and, in some cases, a lattice (for instance, when is the family of the stable sets in a graph). Moreover, one of the bouquets that correspond to the highest elements in the meet semi-lattice provides the smallest decomposition of into matroidal families, such that the rank functions of the different matroids have the same values for common sets. In the last section, we give sharp bounds on the performance of the greedy algorithm, using parameters of some special bouquets in the semi-lattice.