Solving A\underline x =\underline b Using a Modified Conjugate Gradient Method Based on Roots of A

We consider the modified conjugate gradient procedure for solving A = in which the approximation space is based upon the Krylov space associated with A ^1/p and , for any integer p. For the square-root MCG (p=2) we establish a sharpened bound for the error at each iteration via Chebyshev polynomials in . We discuss the implications of the quickly accumulating effect of an error in in the initial stage, and find an error bound even in the presence of such accumulating errors. Although this accumulation of errors may limit the usefulness of this method when is unknown, it may still be successfully applied to a variety of small, almost-SPD problems, and can be used to jump-start the conjugate gradient method. Finally, we verify these theoretical results with numerical tests.     

Stability of Linear Difference and Differential Inclusions

Any given n×n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N×N matrix B of spectral radius (B) arbitrarily close to (A). A difference inclusion , where is a compact set of matrices, is asymptotically stable if and only if can be extended to a set of nonnegative matrices B with or . Similar results are derived for differential inclusions.     

Two-Parameter Discrete Systems over a Residue Ring and Their Properties

A class of two-parameter discrete systems defined on the ring of class of residues of integers modulo m is studied. All solutions are shown to be periodic, stability conditions (equality of solutions to zero, beginning from a certain instant) and a controllability condition are formulated. Controllability is shown to guarantee stabilizability.     

Combining the Perceptron Algorithm with Logarithmic Simulated Annealing

We present results of computational experiments with an extension of the Perceptron algorithm by a special type of simulated annealing. The simulated annealing procedure employs a logarithmic cooling schedule , where is a parameter that depends on the underlying configuration space. For sample sets S of n-dimensional vectors generated by randomly chosen polynomials , we try to approximate the positive and negative examples by linear threshold functions. The approximations are computed by both the classical Perceptron algorithm and our extension with logarithmic cooling schedules. For and , the extension outperforms the classical Perceptron algorithm by about 15% when the sample size is sufficiently large. The parameter was chosen according to estimations of the maximum escape depth from local minima of the associated energy landscape.      

Conditions for Instability of One Class of Nonlinear Nonautomomous Dynamic Systems

Consideration was given to the conditions for instability of the equilibrium states of a nonlinear nonautonomous dynamic systems obeying an ordinary vector differential equation of arbitrary order whose right-hand side satisfies the following conditions: (i) for any t 0, div 0$$ " align="middle" border="0"> almost everywhere on the set H that is a neighborhood of the equilibrium point of the system and (ii) at any point . The equilibrium states of such systems can be both stable and unstable. For one class of these systems, sufficient instability conditions were given, which enables one to carry out studies using only the information about the right-hand side of the system.     

Computation of Battle–Lemarie Wavelets Using an FFT-Based Algorithm

Battle and Lemarie derived independently wavelets by orthonormalizing B-splines. The scaling function _m (t) corresponding to Battle–Lemarie's wavelet _m (t) is given by , where B _m(t) is the mth-order central B-spline and the coefficients _{m, k} satisfy . In this paper, we propose an FFT-based algorithm for computing the expansion coefficients _{m, k} and the two-scale relations of the scaling functions and wavelets. The algorithm is very simple and it can be easily implemented. Moreover, the expansion coefficients can be efficiently and accurately obtained via multiple sets of FFT computations. The computational approach presented in this paper here is noniterative and is more efficient than the matrix approach recently proposed in the literature.     

Computational Finite-Element Schemes for Optimal Control of an Elliptic System with Conjugation Conditions

New optimal control problems are considered for distributed systems described by elliptic equations with conjugate conditions and a quadratic minimized function. Highly accurate computational discretization schemes are constructed for the case where a feasible control set coincides with the full Hilbert space of controls.     

Stability of the Logistic Population Model with Delayed Environmental Response

The population dynamics model , was considered. For this model with uniform distribution of delays and a _n = 0, nonnegativeness and convexity of the sequence a _k (0 k n) was shown to be the sufficient stability condition. Therefore, there is no need to constrain the reproduction rate and the mean delay .     

Adaptive Anomaly Detection in Transaction-Oriented Networks

Adaptive algorithms for real-time and proactive detection of network/service anomalies, i.e., soft performance degradations, in transaction-oriented wide area networks (WANs) have been developed. These algorithms (i) adaptively sample and aggregate raw transaction records to compute service-class based traffic intensities, in which potential network anomalies are highlighted; (ii) construct dynamic and service-class based performance thresholds for detecting network and service anomalies; and (iii) perform service-class based and real-time network anomaly detection. These anomaly detection algorithms are implemented as a real-time software system called TRISTAN ( ansaction n antaneous nomaly otification), which is deployed in the AT&T Transaction Access Services (TAS) network. The TAS network is a commercially important, high volume (millions of transactions per day), multiple service classes (tens), hybrid telecom and data WAN that services transaction traffic such as credit card transactions in the US and neighboring countries. TRISTAN is demonstrated to be capable of automatically and adaptively detecting network/service anomalies and correctly identifying the corresponding "guilty" service classes in TAS. TRISTAN can detect network/service faults that elude detection by the traditional alarm-based network monitoring systems.     

Staircase visibility and computation of kernels

Let be some set of orientations, that is, . We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in . We call such curves -staircases. Two points p andq in a polygonP are said to -see each other if an -staircase fromp toq exists that is completely contained inP. The -kernel of a polygonP is then the set of all points which -see all other points. The -kernel of a simple polygon can be obtained as the intersection of all {}-kernels, with . With the help of this observation we are able to develop an algorithm to compute the -kernel of a simple polygon, for finite . We also show how to compute theexternal -kernel of a polygon in optimal time . The two algorithms are combined to compute the ( -kernel of a polygon with holes in time .This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/5-4 and the Natural Sciences and Engineering Research Council of Canada and Information Technology Research Centre of Ontario.     

Determination of the roots and of the global extremum of a lipschitz function

Conclusion The obvious deficiency of the method (1.3), (1.9) is the possible difficulty of the operation . In connection with this one can note that all the above given statements remain valid if the number is replaced by some positive lower bound of |f(t _k ,x)| on .In computational methods, the presence of the Lipschitz constant is considered as a deficiency. In connection with this we can note that the Lipschitz constant L can be replaced by any of its upper estimates. For example, for a differentiable function f(z) one can take .Translated from Kibernetika, No. 2, pp. 71–74, March–April, 1987.     

An Algebraic Approach to Propositional Fuzzy Logic

We investigate the variety corresponding to a logic (introduced in Esteva and Godo, 1998, and called there), which is the combination of ukasiewicz Logic and Product Logic, and in which Gödel Logic is interpretable. We present an alternative (and slightly simpler) axiomatization of such variety. We also investigate the variety, called the variety of algebras, corresponding to the logic obtained from by the adding of a constant and of a defining axiom for one half. We also connect algebras with structures, called f-semifields, arising from the theory of lattice-ordered rings, and prove that every algebra can be regarded as a structure whose domain is the interval [0, 1] of an f-semifield , and whose operations are the truncations of the operations of to [0, 1]. We prove that such a structure is uniquely determined by up to isomorphism, and we establish an equivalence between the category of algebras and that of f-semifields.     

Lower Bound Methods and Separation Results for On-Line Learning Models

We consider the complexity of concept learning in various common models for on-line learning, focusing on methods for proving lower bounds to the learning complexity of a concept class. Among others, we consider the model for learning with equivalence and membership queries. For this model we give lower bounds on the number of queries that are needed to learn a concept class in terms of the Vapnik-Chervonenkis dimension of , and in terms of the complexity of learning with arbitrary equivalence queries. Furthermore, we survey other known lower bound methods and we exhibit all known relationships between learning complexities in the models considered and some relevant combinatorial parameters. As it turns out, the picture is almost complete. This paper has been written so that it can be read without previous knowledge of Computational Learning Theory.     

A Parallel Logarithmic Order Algorithm for General Multibody System Dynamics

A novel optimal order optimal resource parallel multibody algorithm with general system applicability is derived directly from the sequential recursive methods and the most recent developments in recursive constraint treatments. This new Recursive Coordinate Reduction Parallelism (RCRP) is the first optimal order parallel direct method with a sequential implementation that is exactly the efficient algorithm. Consequently, the RCRP sets new benchmarks for performance over a wide range of problem size and parallel resources. Comparisons to existing methods also demonstrate that the RCRP is presently the best general parallel method.     

Lange and Wiehagen's pattern language learning algorithm: An average-case analysis with respect to its total learning time

The present paper deals with the best-case, worst-case and average-case behavior of Lange and Wiehagen's (1991) pattern language learning algorithm with respect to its total learning time. Pattern languages have been introduced by Angluin (1980) and are defined as follows: Let be any non-empty finite alphabet containing at least two elements. Furthermore, let be an infinite set of variables such that . Patterns are non-empty strings over . L(π), the language generated by pattern π, is the set of strings which can be obtained by substituting non-null strings from for the variables of the pattern π. Lange and Wiehagen's (1991) algorithm learns the class of all pattern languages in the limit from text. We analyze this algorithm with respect to its total learning time behavior, i.e., the overall time taken by the algorithm until convergence. For every pattern π containing k different variables it is shown that the total learning time is in the best-case and unbounded in the worst-case. Furthermore, we estimate the expectation of the total learning time. In particular, it is shown that Lange and Wiehagen's algorithm possesses an expected total learning time of with respect to the uniform distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Quaternary Codes and Biphase Sequences from $$\mathbb{Z}_8 $$ -Codes

Composing the Carlet map with the inverse Gray map, a new family of cyclic quaternary codes is constructed from 5-cyclic -codes. This new family of codes is inspired by the quaternary Shanbag–Kumar–Helleseth family, a recent improvement on the Delsarte–Goethals family. We conjecture that these -codes are not linear. As applications, we construct families of low-correlation quadriphase and biphase sequences.     

On Projection Matrices $$\mathcal{P}^k \to \mathcal{P}^2 ,k = 3,...,6, $$ and their Applications in Computer Vision

Projection matrices from projective spaces have long been used in multiple-view geometry to model the perspective projection created by the pin-hole camera. In this work we introduce higher-dimensional mappings for the representation of various applications in which the world we view is no longer rigid. We also describe the multi-view constraints from these new projection matrices (where k > 3) and methods for extracting the (non-rigid) structure and motion for each application.     

Congruences et Automorphismes des Automates Finis

Summary We study a class of congruences of strongly connected finite automata, called the group congruences, which may be defined in this way: every element fixing any class of the congruence induces a permutation on this class. These congruences form an ideal of the lattice of all congruences of the automaton and we study the group associated with the maximal group congruence (maximal induced group) with respect to the Suschkevitch group of the transition monoid of . The transitivity equivalence of the subgroups of the automorphism group of are found to be the group congruences associated with regular groups, which form also in ideal of the lattice of congruences of . We then characterize the automorphism group of with respect to the maximal induced group. As an application, we show that, given a group G and an automaton , there exists an automaton whose automorphism group is isomorphic to G and such that the quotient by the automorphism congruence is .