Random dynamical systems arising from iterated function systems with place-dependent probabilities

We show that if an iterated function system with place-dependent probabilities admits an invariant and attractive measure, then it has the structure of a random dynamical system (in the sense of Ludwig Arnold).     

Stochastic matrices arising from genetic inheritance

We establish a connection between two different approaches that can be used to describe the same genetic situation. We focus on the notion of coalgebra with genetic realization introduced by Tian and Li and show how their structure constants can be used to characterize different stochastic processes related to the genetic inheritance.     

Hierarchical Preconditioning for PT AP-Systems arising from particulate flows

Particulate flows, i.e. flow of an incompressible, Newtonian carrier fluid loaded with (many) rigid bodies, play an important role in diverse technical applications. In [1] a finite element method was introduced to simulate such flows. The method relies on a splitting method and a subspace projection method to incorporate the rigid body motion of the particles in a so called one domain approach [2]. The resulting systems arising after discretization are ill conditioned in general. Thus preconditioning is mandatory for instance when using an iterative Krylov subspace methods. In this paper we present a Schur complement based preconditioner well suited for this type of application. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Thin Lehman matrices arising from finite groups

Two $n\times n$ $(0\text{,}1)$ matrices $X$, $Y$ are called thin Lehman matrices if they are solutions of the matrix equation ${\mathit{XY}}^T=J_n+I_n$, where $J_n$ is the $n\times n$ matrix of all $1$s and $I_n$ is the identity matrix. These matrices are important in the set covering problem, but few examples are known. In this paper, we will introduce the notion of $1$-overlapped factorizations of finite groups which constructs a new class of thin Lehman matrices. Moreover, we will study some structural properties of $1$-overlapped factorizations.     

Construction of D-optimal designs for N ≡ 2 mod 4 using block-circulant matrices

Circulant matrices of order t with elements circulant matrices of order s are used for the construction of D-optimal saturated designs of order N = 2st. A number of new designs are so constructed. The optimal design for N = 66 is constructed for the first time.     

Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming

We propose to compute the search direction at each interior-point iteration for a linear program via a reduced augmented system that typically has a much smaller dimension than the original augmented system. This reduced system is potentially less susceptible to the ill-conditioning effect of the elements in the (1,1) block of the augmented matrix. A preconditioner is then designed by approximating the block structure of the inverse of the transformed matrix to further improve the spectral properties of the transformed system. The resulting preconditioned system is likely to become better conditioned toward the end of the interior-point algorithm. Capitalizing on the special spectral properties of the transformed matrix, we further proposed a two-phase iterative algorithm that starts by solving the normal equations with PCG in each IPM iteration, and then switches to solve the preconditioned reduced augmented system with symmetric quasi-minimal residual (SQMR) method when it is advantageous to do so. The experimental results have demonstrated that our proposed method is competitive with direct methods in solving large-scale LP problems and a set of highly degenerate LP problems. Research supported in parts by NUS Research Grant R146-000-076-112 and SMA IUP Research Grant.     

On the condition number of matrices arising in the tikhonov regularization method

In this work, we consider the regularization method for linear ill-posed problems. For operators and approximating subspaces satisfying certain conditions and for a specific form of the regularization parameter, upper and lower bounds are given for the condition number of the corresponding discrete problem.     

Exact eigensystems for some matrices arising from discretizations

It is known, for example, that the eigenvalues of the N×N matrix A, arising in the discretization of the wave equation, whose only nonzero entries are A_kk+1=A_k+1k=-1,k=1,…,N-1, and A_kk=2,k=1,…,N, are 2{1-cos[pπ/(N+1)]} with corresponding eigenvectors v^(p) given by . We show by considering a simple finite difference approximation to the second derivative and using the summation formulae for sines and cosines that these and other similar formulae arise in a simple and unified way.     

Galois groups of polynomials arising from circulant matrices

Circulant matrices are used to construct polynomials, associated with Chebyshev polynomials of the first kind, whose roots are real and made explicit. Then the Galois groups of the polynomials are computed, giving rise to new examples of polynomials with cyclic Galois groups and Galois groups of order p(p−1) that are generated by a cycle of length p and a cycle of length p−1.     

On the spectrum of stiffness matrices arising from isogeometric analysis

We study the spectral properties of stiffness matrices that arise in the context of isogeometric analysis for the numerical solution of classical second order elliptic problems. Motivated by the applicative interest in the fast solution of the related linear systems, we are looking for a spectral characterization of the involved matrices. In particular, we investigate non-singularity, conditioning (extremal behavior), spectral distribution in the Weyl sense, as well as clustering of the eigenvalues to a certain (compact) subset of \(\mathbb C\) . All the analysis is related to the notion of symbol in the Toeplitz setting and is carried out both for the cases of 1D and 2D problems.     

The determinants of certain matrices arising from the Boolean lattice

Let B be the Boolean lattice on an n-set with B=?B_i the rank decomposition. Let M(n,i) be the incidence matrix between B_i and B_n−i. We obtain a recursive formula for the determinant of the matrix M(n,i).     

On Hausdorff dimension of invariant measures arising from non-contractive iterated function systems

Under rather general assumptions we give an upper and lower bound estimate of the Hausdorff dimension of the invariant probability measure for an iterated function systems acting on a Polish space. Received: May 2, 2001; in final form: July 30, 2001?Published online: May 29, 2002     

Preconditioning the Poincaré-Steklov operator by using Green's function

This paper is concerned with the Poincaré-Steklov operator that is widely used in domain decomposition methods. It is proved that the inverse of the Poincaré-Steklov operator can be expressed explicitly by an integral operator with a kernel being the Green's function restricted to the interface. As an application, for the discrete Poincaré-Steklov operator with respect to either a line (edge) or a star-shaped web associated with a single vertex point, a preconditioner can be constructed by first imbedding the line as the diameter of a disk, or the web as a union of radii of a disk, and then using the Green's function on the disk. The proposed technique can be effectively used in conjunction with various existing domain decomposition techniques, especially with the methods based on vertex spaces (from multi-subdomain decomposition). Some numerical results are reported.

     

A class of Lie algebras arising from intersection matrices

We find a class of Lie algebras, which are defined from the symmetrizable generalized intersection matrices. However, such algebras are different from generalized intersection matrix algebras and intersection matrix algebras. Moreover, such Lie algebras generated by semi-positive definite matrices can be classified by the modified Dynkin diagrams.     

Dynamical systems arising from random substitutions

Random substitutions are a natural generalisation of their classical ‘deterministic’ counterpart, whereby at every step of iterating the substitution, instead of replacing a letter with a predetermined word, every letter is independently replaced by a word from a finite set of possible words according to a probability distribution. We discuss the subshifts associated with such substitutions and explore the dynamical and ergodic properties of these systems in order to establish the groundwork for their systematic study. Among other results, we show under reasonable conditions that such systems are topologically transitive, have either empty or dense sets of periodic points, have dense sets of linearly repetitive elements, are rarely strictly ergodic, and have positive topological entropy.     

A new approach for solving stokes systems arising from a distributive relaxation method

The distributed relaxation method for the Stokes problem has been advertised as an adequate change of variables that leads to a lower triangular system with Laplace operators on the main diagonal for which multigrid methods are very efficient. We show that under high regularity of the Laplacian, the transformed system admits almost block‐lower triangular form. We analyze the distributed relaxation method and compare it with other iterative methods for solving the Stokes system. We also present numerical experiments illustrating the effectiveness of the transformation which is well established for certain finite difference discretizations of Stokes problems. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 27: 898–914, 2011     

On the mini-computer solution of large systems of linear equations arising from the finite element method

The efficiency of the application of mini-computers to the solution of many problems by means of the finite element method is well recognized, and the importance of the percentage of time devoted to the solution of the resultant systems of linear equations is also noteworthy.Here, we present a comparative study of six programs of the solution of systems of linear equations, implemented in a 64-Kbyte mini-computer (HP1000F). The methods and algorithms on which the programs are based are described.Then, six finite element problems are presented with various degrees of discretization, giving rise to 19 different cases. In each case computation times, the number of disk input-output transfers and the number of arithmetic operations carried out are compared. It is concluded that the programs based on algorithms of variable bandwidth are always superior to those of constant bandwidth. In some cases, the optimum results are obtained with the algorithm of hypermatrices.