共查询到20条相似文献,搜索用时 31 毫秒
1.
Let A=〈a1,a2,…,am〉 and B=〈b1,b2,…,bn〉 be two sequences, where each pair of elements in the sequences is comparable. A common increasing subsequence of A and B is a subsequence 〈ai1=bj1,ai2=bj2,…,ail=bjl〉, where i1<i2<?<il and j1<j2<?<jl, such that for all 1?k<l, we have aik<aik+1. A longest common increasing subsequence of A and B is a common increasing subsequence of the maximum length. This paper presents an algorithm for delivering a longest common increasing subsequence in O(mn) time and O(mn) space. 相似文献
2.
Senol Utku 《Computers & Structures》1973,3(2):419-420
In obtaining the number of eigenvalues greater than a given constant λ0 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–λ0B], 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 λ0 (not an eigenvalue) is the number of positive entries of the diagonal matrix [d] in the identity [A–λ0B] = [u]T[d][u] where [u] is the upper triangular matrix associated with Crout-Banachievicz type decomposition of [A –λ0B], without the help of the separation theorem and the Sturm sequence. 相似文献
3.
We establish structural controllability results for matrix pairs [A, B] where A = A 0 + Σ μ iAi , B = B 0 + σ μ i, Bi , with the Ai , Bi , fixed, and the μ i , free scalar parameters. The results characterize structural controllability in several ways, via tests involving the checking of the rank or the evaluation of the determinant of various constant matrices formed from the Ai , Bi . A number of the results used as intermediate results tests for a full rank property of matrix nets, i.e. tests that check if M = M0+ ΣμiMi prescribed, μ i variable, has full rank for almost all μ i . 相似文献
4.
On the problem of general structural assignments of linear systems through sensor/actuator selection
A systematic method is developed for determining an output matrix C for a given matrix pair (A,B) such that the resulting linear system characterized by the matrix triple (A,B,C) has the pre-specified system structural properties, such as the finite and infinite zero structure and the invertibility structures. Since the matrix C describes the locations of the sensors, the procedure of choosing C is often referred to as sensor selection. The method developed in this paper for sensor selection can be applied to the dual problem of actuator selection, where, for a given matrix pair (A,C), a matrix B is to be determined such that the resulting matrix triple (A,B,C) has the pre-specified structural properties. 相似文献
5.
Approximation algorithms for covering/packing integer programs 总被引:1,自引:0,他引:1
Stavros G. Kolliopoulos 《Journal of Computer and System Sciences》2005,71(4):495-505
Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing . We give a bicriteria-approximation algorithm that, given ε∈(0,1], finds a solution of cost O(ln(m)/ε2) times optimal, meeting the covering constraints (Ax?a) and multiplicity constraints (x?d), and satisfying Bx?(1+ε)b+β, where β is the vector of row sums βi=∑jBij. Here m denotes the number of rows of A.This gives an O(lnm)-approximation algorithm for CIP—minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints Bx?b. The previous best approximation ratio has been O(ln(maxj∑iAij)) since 1982. CIP contains the set cover problem as a special case, so O(lnm)-approximation is the best possible unless P=NP. 相似文献
6.
Th. Beelen 《Systems & Control Letters》1988,10(4)
In this paper we give a new numerical method for constructing a rank m correction BF to an n × n matrix A, such that the generalized eigenvalues of λE−(A+BF) are all at λ = 0. In the control literature, this problem is known as ‘deadbeat control’ of a generalized state-space system Exi+1 = Axi + Bui, whereby the matrix F is the ‘feedback matrix’ to be constructed. 相似文献
7.
Priv.-Doz. Dr. H. Ratschek 《Computing》1972,10(3):245-254
The paper gives necessary and sufficient conditions for the product of two interval polynomials being equal to their formally defined product. For this purpose criteria must be deduced for which intervalsA i, B j the equality(A 1+...+A m ) (B 1 +...+B n )=A 1 B 1 +A 1 B 2 +...+A m B n (relation of distributivity) holds. 相似文献
8.
《Computer Methods in Applied Mechanics and Engineering》1987,62(3):293-303
A sixth-order convergent finite difference method is developed for the numerical solution of the special nonlinear fourth-order boundary value problem y(iv)(x) = f(x, y), a < x < b, y(a) = A0, y″(a) = B0, y(b) = A1 y′(b) = B1, the simple-simple beam problem.The method is based on a second-order convergent method which is used on three grids, sixth-order convergence being obtained by taking a linear combination of the (second-order) numerical results calculated using the three individual grids.Special formulas are proposed for application to points of the discretization adjacent to the boundaries x = a and x= b, the first two terms of the local truncation errors of these formulas being the same as those of the second-order method used at the other points of each grid.Modifications to these two formulas are obtained for problems with boundary conditions of the form y(a) = A0, y′(a) = C0, y(b) = A1, y′(b) = C1, the clamped-clamped beam problem.The general boundary value problem, for which the differential equation is y(iv)(x) = f(x, y, y′, y″, y‴), is also considered. 相似文献
9.
A unit cube in k-dimension (or a k-cube) is defined as the Cartesian product R1×R2×?×Rk, where each Ri is a closed interval on the real line of the form [ai,ai+1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. Many NP-complete graph problems can be solved efficiently or have good approximation ratios in graphs of low cubicity. In most of these cases the first step is to get a low dimensional cube representation of the given graph.It is known that for a graph G, . Recently it has been shown that for a graph G, cub(G)?4(Δ+1)lnn, where n and Δ are the number of vertices and maximum degree of G, respectively. In this paper, we show that for a bipartite graph G=(A∪B,E) with |A|=n1, |B|=n2, n1?n2, and Δ′=min{ΔA,ΔB}, where ΔA=maxa∈Ad(a) and ΔB=maxb∈Bd(b), d(a) and d(b) being the degree of a and b in G, respectively, cub(G)?2(Δ′+2)⌈lnn2⌉. We also give an efficient randomized algorithm to construct the cube representation of G in 3(Δ′+2)⌈lnn2⌉ dimensions. The reader may note that in general Δ′ can be much smaller than Δ. 相似文献
10.
LetA=(a ij ) be the distance matrix of an arbitrary (asymmetric) traveling salesman problem and let τ=τ1τ2...τ m be the optimal solution of the corresponding assignment problem with the subtours τ=τ1τ2...τ m . By choosing (m?1) transpositions (k, l) withk ∈ τ i?1,l ∈ τ i (i=2, ...,m) and patching the subtours by using these transpositions in any order, we get a set of cyclic permutations. It will be shown that within this set of cyclic permutations a tour with minimum distance can be found by O(n 2|τ|* operations, where |τ|* is the maximum number of nodes in a subtour of τ. Moreover, applying this result to the case whenA=(a ij ) is a permuted distribution matrix (Monge-matrix) and thepatching graph G τ is a multipath, a result of Gaikov can be improved: By combining the above theory with a result of Park alinear algorithm for finding an optimal TSP solution can be derived, provided τ is already known. 相似文献
11.
Partial words are finite sequences over a finite alphabet A that may contain a number of “do not know” symbols denoted by ?’s. Setting $A_{\diamond}=A\cup\lbrace{\diamond}\rbracePartial words are finite sequences over a finite alphabet A that may contain a number of “do not know” symbols denoted by ⋄’s. Setting
Aà=Aè{à}A_{\diamond}=A\cup\lbrace{\diamond}\rbrace
, A
⋄
* denotes the set of all partial words over A. In this paper, we investigate the border correlation function
b:Aà*?{a,b}*\beta:A_{\diamond}^{*}\rightarrow\lbrace a,b\rbrace^{*}
that specifies which conjugates (cyclic shifts) of a given partial word w of length n are bordered, that is, β(w)=c
0
c
1…c
n−1 where c
i
=a or c
i
=b according to whether the ith cyclic shift σ
i
(w) of w is unbordered or bordered. A partial word w is bordered if a proper prefix x
1 of w is compatible with a proper suffix x
2 of w, in which case any partial word x containing both x
1 and x
2 is called a border of w. In addition to β, we investigate an extension β′:A
⋄
*→ℕ* that maps a partial word w of length n to m
0
m
1…m
n−1 where m
i
is the length of a shortest border of σ
i
(w). Our results extend those of Harju and Nowotka. 相似文献
12.
This paper is an extension of our previous paper “A program generator for the Incomplete LU-decomposition-Conjugate Gradient (ILUCG) method” which appeared in Computer Physics Communications. In that paper we presented a generator program which produced a code package to solve the system of equations Ax = bb, where A is an arbitrary nonsingular matrix, by the ILUCG method. In the present paper we offer an alternative generator program which produces a code package applicable to the case where A is symmetric and positive definite. The numerical algorithm used is the Incomplete Cholesky Conjugate Gradient (ICCG) method of Meijerink and Van der Vorst which executes approximately twice as fast per iteration as the ILUCG method. In addition, we provide an optional preprocessor to treat the case of a not diagonally dominant nonsymmetric and nonsingular matrix A by solving the equation ATAx = ATb. 相似文献
13.
Controllability for Discrete Systems with a Finite Control Set 总被引:1,自引:1,他引:0
In this paper we consider the problem of controllability for a discrete linear control system x
k+1=Ax
k+Bu
k, u
k∈U, where (A,B) is controllable and U is a finite set. We prove the existence of a finite set U ensuring density for the reachable set from the origin under the necessary assumptions that the pair (A,B) is controllable and A has eigenvalues with modulus greater than or equal to 1. In the case of A only invertible we obtain density on compact sets. We also provide uniformity results with respect to the matrix A and the initial condition. In the one-dimensional case the matrix A reduces to a scalar λ and for λ>1 the reachable set R(0,U) from the origin is?
?When 0<λ<1 and U={0,1,3}, the closure of this set is the subject of investigation of the well-known {0,1,3}-problem. It turns out that the
nondensity of for the finite set of integers is related to special classes of algebraic integers. In particular if λ is a Pisot number, then the set is nowhere dense
in ℝ for any finite control set U of rationals.
Date received: August 19, 1998. Date revised: December 5, 2000. 相似文献
14.
Sebastian Deorowicz 《Information Processing Letters》2006,100(1):14-20
Finding the longest common subsequence (LCS) of two given sequences A=a0a1…am−1 and B=b0b1…bn−1 is an important and well studied problem. We consider its generalization, transposition-invariant LCS (LCTS), which has recently arisen in the field of music information retrieval. In LCTS, we look for the LCS between the sequences A+t=(a0+t)(a1+t)…(am−1+t) and B where t is any integer. We introduce a family of algorithms (motivated by the Hunt-Szymanski scheme for LCS), improving the currently best known complexity from O(mnloglogσ) to O(Dloglogσ+mn), where σ is the alphabet size and D?mn is the total number of dominant matches for all transpositions. Then, we demonstrate experimentally that some of our algorithms outperform the best ones from literature. 相似文献
15.
《Computers & Mathematics with Applications》2003,45(10-11):1655-1672
We derive an algorithm based on the fast Fourier transform to construct a real symmetric matrix S with eigenvalues λ1≥λ2≥⋯≥λn, with eigenvector e = [1, 1, … ,1]T belonging to the eigenvalue λ1.We find simple conditions on the eigenvalues such that the algorithm constructs an irreducible matrix S = λ1E, where E is a symmetric doubly stochastic matrix. 相似文献
16.
G. Stefanidou 《Information Sciences》2006,176(24):3694-3710
We investigate the periodic nature of the positive solutions of the fuzzy difference equation , where k, m are positive integers, A0, A1, are positive fuzzy numbers and the initial values xi, i = −d, −d + 1, … , −1, d = max{k, m}, are positive fuzzy numbers. In addition, we give conditions so that the solutions of this equation are unbounded. 相似文献
17.
We consider finite dimensional nonlinear eigenvalue problems of the typeAu=λFu whereA is a matrix and(Fu) i =f(u i ),i=1, ...,m. These may be thought of as discretizations of a corresponding boundary value problem. We show that positive, spurious solution branches of the discrete equations (which have been observed in some cases in [1, 7]) typically arise iff increases sufficiently strong and ifA ?1 has at least two positive columns of a certain type. We treat in more detail the casesf(u)=e u andf(u)=u α where also discrete bifurcation diagrams are given. 相似文献
18.
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 ∈ ? n 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. 相似文献
19.
20.
Linda J. Hayes 《Mathematics and computers in simulation》1980,22(1):25-29
Numerical results using two modified Crank-Nicolson time discretizations are presented for finite element approximations to the nonlinear parabolic equation in 1Rd, c(x,u) ? (aij (x,u)u,j),i + bi (x,u)u,i = f(x,t,u), where the summation convection on repeated indices is assumed. Both procedures use a local approximation to the coefficients which is based on patches of finite elements. With the first method, the coefficients are updated at each time step; however, only one matrix decomposition is required per problem. This method can exploit efficient direct methods for solving the resulting matrix problem. The second method is an alternating-direction variation which is valid for certain nonrectangular regions. With the alternating-direction method the resulting matrix problem can be solved as a series of one-dimensional problems, which results in a significant savings of time and storage over traditional techniques. 相似文献