On the global behavior of a high-order rational difference equation

In this paper, we consider the (k+1)-order rational difference equation

     

The approximate swap and mismatch edit distance

There is no known algorithm that solves the general case of the approximate edit distance problem, where the edit operations are insertion, deletion, mismatch, and swap, in time o(nm), where n is the length of the text and m is the length of the pattern.In the effort to study this problem, the edit operations have been analyzed independently. Karloff [10] showed an algorithm that approximates the edit distance problem with only the mismatch operation in time . Amir et al. [4] showed that if the only edit operations allowed are swap and mismatch, then the exact edit distance problem can be solved in time .In this paper, we discuss the problem of approximate edit distance with swap and mismatch. We show a randomized time algorithm for the problem. The algorithm guarantees an approximation factor of (1+?) with probability of at least .     

CANM, a program for numerical solution of a system of nonlinear equations using the continuous analog of Newton's method

A FORTRAN program is presented which solves a system of nonlinear simultaneous equations using the continuous analog of Newton's method (CANM). The user has the option of either to provide a subroutine which calculates the Jacobian matrix or allow the program to calculate it by a forward-difference approximation. Five iterative schemes using different algorithms of determining adaptive step size of the CANM process are implemented in the program.

Program summary

Title of program: CANMCatalogue number: ADSNProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADSNProgram available from: CPC Program Library, Queen's University of Belfast, Northern IrelandLicensing provisions: noneComputer for which the program is designed and others on which it has been tested:Computers: IBM RS/6000 Model 320H, SGI Origin2000, SGI Octane, HP 9000/755, Intel Pentium IV PCInstallation: Department of Chemistry, University of Toronto, Toronto, CanadaOperating systems under which the program has been tested: IRIX64 6.1, 6.4 and 6.5, AIX 3.4, HP-UX 9.01, Linux 2.4.7Programming language used: FORTRAN 90Memory required to execute with typical data: depends on the number of nonlinear equations in a system. Test run requires 80 KBNo. of bits in distributed program including test data, etc.: 15283Distribution format: tar gz formatNo. of lines in distributed program, including test data, etc.: 1794Peripherals used: line printer, scratch disc storeExternal subprograms used: DGECO and DGESL [1]Keywords: nonlinear equations, Newton's method, continuous analog of Newton's method, continuous parameter, evolutionary differential equation, Euler's methodNature of physical problem: System of nonlinear simultaneous equations

     

Approximating a similarity matrix by a latent class model: A reappraisal of additive fuzzy clustering

Let be a given n×n square symmetric matrix of nonnegative elements between 0 and 1, similarities. Fuzzy clustering results in fuzzy assignment of individuals to K clusters. In additive fuzzy clustering, the n×K fuzzy memberships matrix is found by least-squares approximation of the off-diagonal elements of by inner products of rows of . By contrast, kernelized fuzzy c-means is not least-squares and requires an additional fuzziness parameter. The aim is to popularize additive fuzzy clustering by interpreting it as a latent class model, whereby the elements of are modeled as the probability that two individuals share the same class on the basis of the assignment probability matrix . Two new algorithms are provided, a brute force genetic algorithm (differential evolution) and an iterative row-wise quadratic programming algorithm of which the latter is the more effective. Simulations showed that (1) the method usually has a unique solution, except in special cases, (2) both algorithms reached this solution from random restarts and (3) the number of clusters can be well estimated by AIC. Additive fuzzy clustering is computationally efficient and combines attractive features of both the vector model and the cluster model.