Calculating the Galois Group of Y′ = = = AY + + + B,Y′ = = = AY Completely Reducible

We consider a special case of the problem of computing the Galois group of a system of linear ordinary differential equations Y′ = MY, M C (x)^{n × n}. We assume that C is a computable, characteristic-zero, algebraically closed constant field with a factorization algorithm. There exists a decision procedure, due to Compoint and Singer, to compute the group in case the system is completely reducible. Berman and Singer (1999, J. Pure Appl. Algebr., 139, 3–23) address the case in which M = [yjsco5390x.gif M 1 * 0 M 2 ], Y′ = M_iY completely reducible for i = 1, 2. Their article shows how to reduce that case to the case of an inhomogeneous system Y′ = AY + B, A C (x)^{n × n}, B C (x)ⁿ, Y′ = AY completely reducible. Their article further presents a decision procedure to reduce this inhomogeneous case to the case of the associated homogeneous system Y′ = AY. The latter reduction involves using a cyclic-vector algorithm to find an equivalent inhomogeneous scalar equation L(y) = b,L C(x)[ D ], b C (x), then computing a certain set of factorizations of L in C(x)[D ]; this set is very large and difficult to compute in general. In this article, we give a new and more efficient algorithm to reduce the case of a system Y′ = AY + B,Y′ = AY completely reducible, to that of the associated homogeneous systemY′ = AY. The new method’s improved efficiency comes from replacing the large set of factorizations required by the Berman–Singer method with a single block-diagonal decomposition of the coefficient matrix satisfying certain properties.     

A spectral characterization of H-optimal feedback performance and its efficient computation

We study the spectral properties of a ‘Toeplitz⁺ Hankel’ operator which arises in the context of the mixed-sensitivity H^∞-optimization problem and whose largest eigenvalue characterizes the optimal achievable performance ε₀. The existence of such an operator was first shown by Verma and Jonckheere [26], who also'noted the potential numerical advantage of computing eo through its eigenvalue characterization rather than through the ε-iteration. Here, we investigate this operator in detail, with the objective of efficiency computing its spectrum. We define an ‘adjoint’ linear-quadratic problem that involves the same ‘Toeplitz⁺ Hankel’ operator, as shown by Jonckheere and Silverman [13–16]. Consequently, a finite polynomial algorithm allows ε₀ to be characterized as simply as the largest root of a polynomial. Finally, a computationally more attractive state space algorithm emerges from the H^t8/LQ relationship. This algorithm yields a very good accuracy evaluation of the performance ε₀ by solving just one algebraic Riccati equation. Thorough exploitation of this algorithm results in a drastic computation reduction with respect to the standard e-iteration.     

Algorithm for Computing Bernstein–Sato Ideals Associated with a Polynomial Mapping

Let f₁, . . . , f_pbe polynomials in n variables with coefficients in a fieldK. We associate with these polynomials a number of functional equations and related ideals B, B_jand BΣ ofK[ s₁, . . . , s_p] called Bernstein–Sato ideals. Using standard basis techniques, our aim is to present an algorithm for computing generators of B_jand BΣ.     

Primality testing with fewer random bits

In the usual formulations of the Miller-Rabin and Solovay-Strassen primality testing algorithms for a numbern, the algorithm chooses candidatesx ₁,x ₂, ...,x _k uniformly and independently at random from _n , and tests if any is a witness to the compositeness ofn. For either algorithm, the probabilty that it errs is at most 2^–k .In this paper, we study the error probabilities of these algorithms when the candidates are instead chosen asx, x+1, ..., x+k–1, wherex is chosen uniformly at random from _n . We prove that fork=[1/2log₂ n], the error probability of the Miller-Rabin test is no more thann ^–1/2+o(1), which improves on the boundn ^–1/4+o(1) previously obtained by Bach. We prove similar bounds for the Solovay-Strassen test, but they are not quite as strong; in particular, we only obtain a bound ofn ^–1/2+o(1) if the number of distinct prime factors ofn iso(logn/loglogn).     

On efficient implementation of an approximation algorithm for the Steiner tree problem

Summary This paper studies the design and implementation of an approximation algorithm for the Steiner tree problem. Given any undirected distance graph G and a set of Steiner points S, the algorithm produces a Steiner tree with total weight on its edges no more than 2(1–1/L) times the total weight on the optimal Steiner tree, where L is the number of leaves in the optimal Steiner tree. Our implementation of the algorithm, in the worst case, makes it run in 0(¦E _g¦+¦V _g–S¦log¦V _g–S¦+¦S¦log ¦S¦) time for general graph G and in 0(¦S¦ log¦S¦+M log (M,¦V _g–S¦)) time for sparse graph G, where E _g is the set of edges in G, V_g is the set of vertices in G, M = min {¦E _g, (¦V _g–S¦–1)²/2} and (x,y) = min {i¦log⁽ⁱ⁾ y x/y}.The implementation is not likely to be improved significantly without the improvement of the shortest paths algorithm and the minimum spanning tree algorithm as the algorithm essentially composes of the computation of the multiple sources shortest paths of a graph with ¦V _g¦ vertices and ¦E _g¦ edges and the minimum spanning tree of a graph with ¦V _g–S¦ vertices and M edges.     

Efficient Algorithms for k-Terminal Cuts on Planar Graphs

The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we give a min{O(n ² log n logm), O(m ² n ^1.5 log² n + k n)} time algorithm with a (2–2/k)-approximation ratio (clearly, m \le k). For the case when all k terminals are covered by the boundary of one face of G, we give an O(n k3 + (n log n)k ²) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when they are applied to planar graphs. To our best knowledge, no previous approximation algorithms specifically for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation algorithm of Dahlhaus et al. (for general graphs) takes O(k n ² log n) time when applied to planar graphs. Our approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm) factor (m \le k).     

A spreadsheet program to optimize kinetic parameters of organic matter from laboratory pyrolysis data

Transformation of sedimentary organic matter (OM) to hydrocarbons is best modeled by assuming the total reaction suite consists of parallel degradations of ‘i’ hypothetical components following the Arrhenius equation and first order kinetics. A kerogen can be defined by characterizing each constituent component by its activation energy (Ei) their initial potentials (Xios) and a single frequency factor (A). We present a user friendly Lotus 1-2-3 program to determine A, Ei and Xio distribution of OMs using a multiple linear regression utility and programmed macros. Rock Eval (RE) S₂ curves of three heating rates are required. Equally spaced time/temperature and peak height data for S₂ curves of ‘n’ temperature steps in increasing order of heating rates are the inputs for the program. The fraction of hydrocarbon generated (f) from 19 hypothetical components of Ei 30, 32,34…78 Kcal/mole for ‘n’ temperature/time steps, by using frequency factor (A) value and assuming Xios=1, are calculated and set up in a ‘n×19’ matrix (matrix M). The fraction of total hydrocarbon generated (f) at ‘n’ temperature steps, obtained from the observed peak heights, are set up in a ‘n×1’ matrix (matrix L). Matrix M is suitably reduced by the program to ‘n×k’ matrix (matrix N) where ‘k’ is a variable, facilitating matrix inversion. Regressing matrix N against matrix L by the program, gives the Xios for ‘k’ Ei components along with a standard error (ERR) of Y estimates and R². Xios and A are then optimized iteratively by varying A values and selecting the solution associated with the lowest ERR value. Results of applying the program on data sets of two widely different types of samples from Indian basins are shown. They match the results obtained from the more sophisticated proprietary software.     

Control chart and stochastic control processes

In this paper, we shall discuss the relation between the expected cost model for a process and the probabilistic control model, whose mean is controlled by an chart.T. Odanaka has exploited the problem of minimizing the membership function or the probability that the performance level of the machine will run out of range in a fuzzy environment. This paper considers the same basic problem of the expected cost model, modified to include the set up costs for controlling the action in any period. The expected cost comprises the fixed and variable cost of taking a control action, the cost of sampling, the cost of investigating the process when the control chart indicates that the process parameters exceed the specified bound, and the cost of producing defective units. Dynamic programming can be used to determine optimal control policies for models where control produces economically measurable benefits and/or costs. When the controlling action incurs a set up charge, the optimal policies are found to be characterized by a pair (s_n, S_n, S′_n, s′_n), where the action is made in a period n to state S_n or S′_n(S_n < S′_n), if the state is found to be outside s_n or s′_n(s_n < s′_n). This statement is subject to a set of basic assumptions such that proportional costs of changing the state variable are zero, the two fixed costs are equal, the loss function is symmetric quasi-convex and the problem's probability densities are quasi-concave.     

System identification of a novel 6-DOF precision positioning table

The purpose of this study is to identify a novel 6-DOF precision positioning table, which is assembled by two different 3-DOF precision positioning tables: a plane-type 3-DOF (X, Y, θ_z) precision positioning table and a cylinder-type 3-DOF (θ_x, θ_y, Z) one. According to the dynamics of a mechanical mass-spring system, we establish simple mathematical equations that contain linear mass (inertia), viscous friction, and spring stiffness associated with cross-coupling effects due to mechanical bending. In system identification, we identify parameters of this 6-DOF and two 3-DOF precision positioning tables driven by piezoelectric actuators with hysteresis phenomenon, which is described by Bouc–Wen model. The identification method based on the real-coded genetic algorithm (RGA) has the advantages to identify all the parameters of the table and the hysteresis model simultaneously. From experimental results and numerical simulations, it is found that the numerically identified parameters are almost the same as those of the real system. In comparison of the identified results between the integral and individual tables, it is found that the integral table has better performance than those from the individual table.     

How to Recognize Zero

An elementary point is a point in complexnspace, which is an isolated, nonsingular solution ofnequations innvariables, each equation being either of the formp = 0, wherepis a polynomial in [x₁,…,x_n], or of the formx_j − e^x_i = 0. An elementary number is the polynomial image of an elementary point. In this article a semi algorithm is given to decide whether or not a given elementary number is zero. It is proved that this semi algorithm is an algorithm, i.e. that it always terminates, unless it is given a problem containing a counterexample to Schanuel’s conjecture.     

Some counterexamples in robust stability theory

This note deals with the problem of determining if a linear system whose characteristics polynomial depends multilinearly on n independent uncertain real parameters Δ_i, I = 1,…,n, is robustly stable. It is shown by example that a polynomial in n variables may have a unique real root, and that this observation disposes of several natural conjectures in robust stability theory. In particular, we show that, in a certain sense, there are no ‘edge’ or ‘m-dimensional face’ Kharitonov-like theorems for the general multilinear case. The result holds even when restricted to that subset of multilinear functions which can be written in the form f(Δ₁,…, Δ_n) = det(I + diag(Δ₁,…,Δ_n)M) for some complex matrix M.     

Speed–accuracy tradeoff in Fitts’ law tasks—on the equivalency of actual and nominal pointing precision

Pointing tasks in human–computer interaction obey certain speed–accuracy tradeoff rules. In general, the more accurate the task to be accomplished, the longer it takes and vice versa. Fitts’ law models the speed–accuracy tradeoff effect in pointing as imposed by the task parameters, through Fitts’ index of difficulty (I_d) based on the ratio of the nominal movement distance and the size of the target. Operating with different speed or accuracy biases, performers may utilize more or less area than the target specifies, introducing another subjective layer of speed–accuracy tradeoff relative to the task specification. A conventional approach to overcome the impact of the subjective layer of speed–accuracy tradeoff is to use the a posteriori “effective” pointing precision W_e in lieu of the nominal target width W. Such an approach has lacked a theoretical or empirical foundation. This study investigates the nature and the relationship of the two layers of speed–accuracy tradeoff by systematically controlling both I_d and the index of target utilization I_u in a set of four experiments. Their results show that the impacts of the two layers of speed–accuracy tradeoff are not fundamentally equivalent. The use of W_e could indeed compensate for the difference in target utilization, but not completely. More logical Fitts’ law parameter estimates can be obtained by the W_e adjustment, although its use also lowers the correlation between pointing time and the index of difficulty. The study also shows the complex interaction effect between I_d and I_u, suggesting that a simple and complete model accommodating both layers of speed–accuracy tradeoff may not exist.     

Edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition-generating trees

The Cayley graphs on the symmetric group plays an important role in the study of Cayley graphs as interconnection networks. Let Cay(S_n, B) be the Cayley graphs generated by transposition-generating trees. It is known that for any F?E(Cay(S_n, B)), if |F|≤n?3 and n≥4, then there exists a hamiltonian cycle in Cay(Sn, B)?F. In this paper, we show that Cay(S_n, B)?F is bipancyclic if Cay(S_n, B) is not a star graph, for n≥4 and |F|≤n?3.     

Sample complexity of worst-case H-identification

We show that the sample complexity of qorst-case H^∞-identification is of order n², by proving that the minimal length of a fractional H^∞-cover for C_n, regarded as the linear space of complex-valued sequences of length n, is of order n². A unit vector u in ^∞ is a fractional H^∞-cover for C_n if for some

Full-size image

for all rh ε C_n, where is the z-transform of h. We also give similar results for real-valued sequences.     

An alternative solution to the H∞-optimal control problem

In this paper we present an alternative solution to the problem min _{X ε H^n×n∞} |A + BXC|_∞ where A, B, rmand C are rational matrices in H^n×n_∞. The solution circumvents the need to extract the matrix inner factors of B and C, providing a multivariable extension of Sarason's H^∞-interpolation theory [1] to the case of matrix-valued B(s) and C(s). The result has application to the diagonally-scaled optimization problem int |D(A + BXC)D⁻¹|_∞, where the infimum is over D, X εH^n×n_∞, D diagonal.     

On the Power of Multiple Reads in a Chip

A chip algorithm is called r-multilective if it reads its input bits r times. In this paper we relate the r-bound communication complexity of a language L and the area requirement for an r-multilective chip algorithm of a related language . More specifically Improving known lower bounds on the r-bound communication complexity of certain languages, we obtain several hierarchies of r-multilective languages depending on the parameter r. For example, if 0 < r < s, then there are constants 0 < c, c′ such that for infinitely many n there is a language L_n {0, 1}ⁿ such that there is an s-multilective algorithm recognizing L_n using area at most c log n and any r-multilective algoerithm recognizing L_n requires area at least c′n/log n. Similar results have been known only for s = 2 and r = 1 and have been open in other cases.     

An estimate on the convergence of MKZ–Bézier operators

The pointwise approximation properties of the MKZ–Bézier operators M_n,α(f,x) for α≥1 have been studied in [X.M. Zeng, Rates of approximation of bounded variation functions by two generalized Meyer–König–Zeller type operators, Comput. Math. Appl. 39 (2000) 1–13]. The aim of this paper is to study the pointwise approximation of the operators M_n,α(f,x) for the other case 0<α<1. By means of some new estimate techniques and a result of Guo and Qi [S. Guo, Q. Qi, The moments for the Meyer–König and Zeller operators, Appl. Math. Lett. 20 (2007) 719–722], we establish an estimate formula on the rate of convergence of the operators M_n,α(f,x) for the case 0<α<1.     

On the Construction of Classes of Suffix Trees for Square Matrices: Algorithms and Applications

We provide a uniform framework for the study of index data structures for a two-dimensional matrixTEXT[1:n, 1:n] whose entries are drawn from an ordered alphabetΣ. An index forTEXTcan be informally seen as the two-dimensional analog of the suffix tree for a string. It allows on-line searches and statistics to be performed onTEXTby representing compactly theΘ(n³) square submatrices ofTEXTin optimalO(n²) space. We identify 4ⁿ⁻¹families of indices forTEXT, each containing ∏ⁿ_i=1 (2i−1)! isomorphic data structures. We also develop techniques leading to a single algorithm that efficiently builds any index in any family inO(n² log n) time andO(n²) space. Such an algorithm improves in various respects the algorithms for the construction of the PAT tree and the Lsuffix tree. The framework and the algorithm easily generalize tod>2 dimensions. Moreover, as part of our algorithm, we provide new algorithmic tools that yield a space-efficient implementation of the “naming scheme” of R. Karpet al.(in“Proceedings, Fourth Symposium on Theory of Computing,” pp. 125–136) for strings and matrices.     

Inductive Constructions of Perfect Ternary Constant-Weight Codes with Distance 3

We propose inductive constructions of perfect (n,3;n – 1)₃ codes (ternary constant-weight codes of length n and weight n – 1 with distance 3), which are modifications of constructions of perfect binary codes. The construction yields at least different perfect (n,3;n – 1)₃ codes. To perfect (n,3;n – 1)₃ codes, perfect matchings in a binary hypercube without close (at distance 1 or 2 from each other) parallel edges are equivalent.