Eine Anwendung des Brouwerschen Fixpunktsatzes in der Intervallarithmetik der Matrizen

A theorem is proved by means of Brouwer's theorem which allows to decide whether a given interval matrix [S] has the inclusion property relative to the unknown inverseA ^?1 of a known matrixA. It is demonstrated in which cases the theorem may be used and how to choose [S] in these cases.     

Matrix computation of subresultant polynomial remainder sequences in integral domains

We present an improved variant of the matrix-triangularization subresultant prs method [1] for the computation of a greatest common divisor of two polynomialsA andB (of degreesm andn, respectively) along with their polynomial remainder sequence. It is improved in the sense that we obtain complete theoretical results, independent of Van Vleck’s theorem [13] (which is not always true [2, 6]), and, instead of transforming a matrix of order 2·max(m, n) [1], we are now transforming a matrix of orderm+n. An example is also included to clarify the concepts.     

Convergence of bpsd method for T (q,r) matrix

In this paper, we obtain a necessary and sufficient condition, when the coefficient matrix A of the equation Ax = f considered is a T(l, 1) matrix, a sufficient condition, when A is a T(l, 2) or T(2, 1) matrix for the convergence of BPSD method. We also obtain the optimum parameters and the optimum rate of convergence of BPSD method, when A is T(l, 1) matrix and a necessary and sufficient condition, when A is positive definite and we point out that the necessary and sufficient condition in [1] and [9] is only sufficient.     

Ring models for delay-differential systems

This paper studies the algebraic structure of linear systems defined over R[λ], the ring of polynomials in λ with real coefficients. Natural definitions of controllability and observability are introduced and properties of R[λ]-transfer matrix realizations are discussed. It is shown that (A_n×n,D_n×m) is a controllable R[λ]-matrix pair if and only if for each set of polynomialsβ₁,β₂,…,β_n, in R[λ] there exists an R[λ] feedback matrixF such that detsI?A?BF]=∏i=1n(s+β_i). By regarding λ as a suitably defined delay operator, it is explained how this result might be applied to delay-differential systems in order to control dynamic response.     

Sturm sequences or law of inertia of quadratic forms?

In obtaining the number of eigenvalues greater than a given constant λ₀ of the eigenvalue problem [A]{x} = λ[B]{x} with [A] and [B] real, symmetric, and [B] positive definite, one usually refers to the Sturm sequence established by the leading principal minors of [A–λ₀B], the proof of which is given basically when the associated special eigenvalue problem is tridiagonal. In this work, using the law of inertia of quadratic forms, it is shown that the number of eigenvalues of [A]{x}] = λ[B]{x} greater than a given constant λ₀ (not an eigenvalue) is the number of positive entries of the diagonal matrix [d] in the identity [A–λ₀B] = [u]^T[d][u] where [u] is the upper triangular matrix associated with Crout-Banachievicz type decomposition of [A –λ₀B], without the help of the separation theorem and the Sturm sequence.     

A(α)-stable cyclic composite multistep methods of order 5

We describe a newA(α)-stable 3-cyclic 3-step method with accuracy of orderP=5. This is in contrast to the originally developed methods [5] which have greater order of accuracy (P=6) but a small stability region. Moreover, the new method shows slightly better stability than the backward differentiation formula (BDF) [6] of the same order.     

A note on compressed sensing and the complexity of matrix multiplication

We consider the conjectured O(N2+?) time complexity of multiplying any two N×N matrices A and B. Our main result is a deterministic Compressed Sensing (CS) algorithm that both rapidly and accurately computes A⋅B provided that the resulting matrix product is sparse/compressible. As a consequence of our main result we increase the class of matrices A, for any given N×N matrix B, which allows the exact computation of A⋅B to be carried out using the conjectured O(N2+?) operations. Additionally, in the process of developing our matrix multiplication procedure, we present a modified version of Indyk's recently proposed extractor-based CS algorithm [P. Indyk, Explicit constructions for compressed sensing of sparse signals, in: SODA, 2008] which is resilient to noise.     

Fuzzy dual-factor time-series for stock index forecasting

There is an old Wall Street adage goes, “It takes volume to make price move”. The contemporaneous relation between trading volume and stock returns has been studied since stock markets were first opened. Recent researchers such as Wang and Chin [Wang, C. Y., & Chin S. T. (2004). Profitability of return and volume-based investment strategies in China’s stock market. Pacific-Basin Finace Journal, 12, 541–564], Hodgson et al. [Hodgson, A., Masih, A. M. M., & Masih, R. (2006). Futures trading volume as a determinant of prices in different momentum phases. International Review of Financial Analysis, 15, 68–85], and Ting [Ting, J. J. L. (2003). Causalities of the Taiwan stock market. Physica A, 324, 285–295] have found the correlation between stock volume and price in stock markets. To verify this saying, in this paper, we propose a dual-factor modified fuzzy time-series model, which take stock index and trading volume as forecasting factors to predict stock index. In empirical analysis, we employ the TAIEX (Taiwan stock exchange capitalization weighted stock index) and NASDAQ (National Association of Securities Dealers Automated Quotations) as experimental datasets and two multiple-factor models, Chen’s [Chen, S. M. (2000). Temperature prediction using fuzzy time-series. IEEE Transactions on Cybernetics, 30 (2), 263–275] and Huarng and Yu’s [Huarng, K. H., & Yu, H. K. (2005). A type 2 fuzzy time-series model for stock index forecasting. Physica A, 353, 445–462], as comparison models. The experimental results indicate that the proposed model outperforms the listing models and the employed factors, stock index and the volume technical indicator, VR(t), are effective in stock index forecasting.     

The accelerated overrelaxation quadrant interlocking iterative method

In this paper we use a new splitting of the matrix A of the linear system A x = b introduced in [1] and we present a new version of the AOR method, more suitable for parallel processing, which involves explicit evaluation of 2 × 2 blocks.

We also obtain several convergence conditions for this new method, when the matrix A of (1.1) belongs to different classes of matrices. Some results, given in [1], are also improved and generalised.     

A note on the Consecutive Ones Submatrix problem

A binary matrix has the Consecutive Ones Property (C1P) for columns if there exists a permutation of its rows that leaves the 1's consecutive in every column. The problem of Consecutive Ones Property for a matrix is a special variant of Consecutive Ones Submatrix problem in which a positive integer K is given and we want to know if there exists a submatrix B of A consisting of K columns of A with C1P property. This paper presents an error in the proof of NP-completeness for this problem in the reference cited in text by Garey and Johnson [Computers and Intractability, A Guide to the Theory of NP-Completeness, 1979].     

Enclosing Solutions of Singular Interval Systems Iteratively

Richardson splitting applied to a consistent system of linear equations Cx = b with a singular matrix C yields to an iterative method x^k+1 = Ax^k + b where A has the eigenvalue one. It is known that each sequence of iterates is convergent to a vector x^* = x^* (x⁰) if and only if A is semi-convergent. In order to enclose such vectors we consider the corresponding interval iteration with (|[A]|) = 1 where |[A]| denotes the absolute value of the interval matrix [A]. If |[A]| is irreducible we derive a necessary and sufficient criterion for the existence of a limit of each sequence of interval iterates. We describe the shape of and give a connection between the convergence of ( ) and the convergence of the powers of [A].Dedicated to Professor G. Mae on the occasion of his 65^th birthday     

Mappings of linear vector spaces induced by a transformation matrix and its applications†

The projections of a vector Ax along a certain orthonormal basis are chosen as the n components of a vector ρ. As the vector x sweeps the n–dimensional space, the locus of the point vector ρ is a closed surface, called the ρ locus. Some of the properties of the ρ locus are similar to those of the eigenvalues of the A matrix. These properties are exploited in the analysis of the unforced, linear time-invariant, dynamical system given by [xdot] = Ax and for the forced systems of the [xdot] = Ax + Bu, where u represents an impulse, step, ramp or sinusoidal input.     

Effect of the Reynolds number on streamline bifurcations in a double-lid-driven cavity with free surfaces

The two-dimensional Navier-Stokes equations for a Newtonian fluid in the absence of body forces are considered in a rectangular double-lid-driven cavity with free surface side walls, the cavity aspect ratio A and three cases of the ratio (S=0,−1,1) of the upper to the lower lid speed. Using a finite element formulation with a mesh which is adaptively refined to facilitate the location of stagnation points, the effect of Reynolds numbers (Re) in the range [0,100] on the streamline patterns and their bifurcations is investigated as A is varied for each S. For Re→0 and each S as A is decreased, a sequence of pitchfork bifurcations at a stagnation point on x=0 is identified as seen in the work of Gaskell et al. [Proc Instn Mech Engrs Sci Part C 212 (1998) 387]. As Re increases for S=0 and decreasing A the stagnation point on x=0 disappears and away from x=0 cusp (saddle-node) bifurcations arise rather than the pitchfork bifurcation whereas for S=−1 and Re∈[0,100] the origin is always a stagnation point at which the same type of bifurcations arises.     

Structure-preserving numerical algorithm for solving discrete-time LMI and DARS

We present a numerical algorithm to solve a discrete-time linear matrix inequality (LMI) and discrete-time algebraic Riccati system (DARS). With a given system (A,B,C,D) we associate a para-hermitian matrix pencil. Then we transform it by an orthogonal transformation matrix into a block-triangular para-hermitian form. Under either of the two assumptions (1) matrix pair (A,B) is controllable or (2) matrix pair (A,B) is reachable and (A,B,C,D) is a left invertible system, we extract the solution of LMI and DARS by the entries of the orthogonal transformation matrix.     

On the construction of real canonical forms of Hamiltonian matrices whose spectrum is an imaginary pair

If A is a Hamiltonian matrix and P a symplectic matrix, the product P⁻¹AP is a Hamiltonian matrix. In this paper, we consider the case where the matrix A has a pair of imaginary eigenvalues and develop an algorithm which finds a matrix P such that the matrix P⁻¹AP has a particularly simple form, a canonical form.     

On the construction of stabilizer codes with an arbitrary binary matrix

This paper proposes a simple framework for constructing a stabilizer code with an arbitrary binary matrix. We define a relation between A ₁ and A ₂ of a binary check matrix A = (A ₁|A ₂) associated with stabilizer generators of a quantum error-correcting code. Given an arbitrary binary matrix, we can derive a pair of A ₁ and A ₂ by the relation. As examples, we illustrate two kinds of stabilizer codes: quantum LDPC codes and quantum convolutional codes. By the nature of the proposed framework, the stabilizer codes covered in this paper belong to general stabilizer (non-CSS) codes.     

On relativizing auxiliary pushdown machines

We consider relativizing the constructions of Cook in [4] characterizing space-bounded auxiliary pushdown automata in terms of timebounded computers. LetS(n) ≥ logn be a measurable space bound. LetDT ^A[NT^A] be the class of setsS such that there exists a machineM such thatM with oracleA recognizes the setS andM is a deterministic [nondeterministic] oracle Turing machine acceptor that runs in time 2 ^cS(n) for some constantc. LetDB _i ^A [NB _i ^A ] be the class of setsS such that there exists a machineM such thatM with oracleA recognizes the setS andM is a deterministic [non-deterministic] oracle Turing machine acceptor with auxiliary pushdown that runs in spaceS(n) and never queries the oracle about strings longer than:S(n) ifi = 1, 2 ^cS(n) for some constantc, ifi = 2, + ∞ ifi = 3. Then we prove the following results: These contrast with Cook's (unrelativized) result:DT = NB = DB.     

On the parameterized complexity of d-dimensional point set pattern matching

Deciding whether two n-point sets A,B∈Rd are congruent is a fundamental problem in geometric pattern matching. When the dimension d is unbounded, the problem is equivalent to graph isomorphism and is conjectured to be in FPT.When |A|=m<|B|=n, the problem becomes that of deciding whether A is congruent to a subset of B and is known to be NP-complete. We show that point subset congruence, with d as a parameter, is W[1]-hard, and that it cannot be solved in O(mno(d))-time, unless SNP⊂DTIME(²o(n)). This shows that, unless FPT=W[1], the problem of finding an isometry of A that minimizes its directed Hausdorff distance, or its Earth Mover's Distance, to B, is not in FPT.     

The generalized eigenvalue problem and acoustic surface wave computations

Numerical aspects of the generalized eigenvalue problemA _μ c=0 are discussed whereA _μ is a parameter-dependent matrix. Instead of determinants, the use of the smallest diagonal element ofR resp.U in theQR resp.LU decomposition is recommended. This idea has first been used by Kublanovskaya [7]. The behaviour of this smallest diagonal element is considered, and several iterative procedures are constructed and discussed. The methods are applied to the computation of acoustic surface waves in layered systems of piezoelectric media where they prove to be powerful. In this part also the special case whenA _μ is a matrix polynomial is mentioned.     

On the RAS-algorithm

Given a nonnegative real (m, n) matrixA and positive vectorsu, v, then the biproportional constrained matrix problem is to find a nonnegative (m, n) matrixB such thatB=diag (x) A diag (y) holds for some vectorsx ∈ ? ^m andy ∈ ? ⁿ and the row (column) sums ofB equalu _i (v _j )i=1,...,m(j=1,..., n). A solution procedure (called the RAS-method) was proposed by Bacharach [1] to solve this problem. The main disadvantage of this algorithm is, that round-off errors slow down the convergence. Here we present a modified RAS-method which together with several other improvements overcomes this disadvantage.