S. Lie found in 1883 the general form of all second-order ordinary differential equations transformable to the linear equation by a change of variables and proved that their solution reduces to integration of a linear third-order ordinary differential equation. He showed that the linearizable equations are at most cubic in the first-order derivative and described a general procedure for constructing linearizing transformations by using an over-determined system of four equations. We present here a simple geometric proof of the theorem, known as Lie's linearization test, stating that the compatibility of Lie's four auxiliary equations furnishes a necessary and sufficient condition for linearization.
The second-order ordinary differential equations can have one, two, three or eight independent symmetries. Sophus Lie showed that the equations with eight symmetries and only these equations can be linearized by a change of variables. Moreover he demonstrated that these equations are at most cubic in the first derivative and gave a convenient invariant description of all linearizable equations. We provide a similar description of the equations with three symmetries. There are four different types of such equations. Classes of equations belonging to one of these types were studied in N.H. Ibragimov and S.V. Meleshko, Invariants and invariant description of second-order ODEs with three infinitesimal symmetries. I, Communications in Nonlinear Science and Numerical Simulation, Vol. 12, No. 8, 2007, pp. 1370--1378. Namely, we presented there the candidates for all four types and studied one of these candidates.The present paper is devoted to other three candidates.
Criteria for second-order ordinary differential equations be linearizable after differentiating or after the Ricatti substitution are given.
We present here the complete solution to the problem on linearization of third-order equations by means of general point transformations. We also formulate the criteria for reducing third-order equations to the equation y''' = 0 by contact transformations.
We present here the solution of the problem on linearization of third-order ordinary differential equations by means of point and contact transformations. We provide, in explicit forms, the necessary and sufficient conditions for linearization, the equations for determining the linearizing point and contact transformations as well as the coefficients of the resulting linear equations.
We present here the necessary and sufficient conditions for linearization of third-order equations by means of point transformations. We show that all third-order equations that are linearizable by point transformations are contained either in the class of equations which are linear in the second-order derivative, or in the class of equations which are quadratic in the second-order derivative. We provide the linearization test for each of these classes and describe the procedure for obtaining the linearizing point transformations as well as the linearized equation.
The main feature of equations of the form y''=H(y) is that their solutions can be represented in quadratures. The paper gives criteria for a second-order ordinary differential equation to be equivalent to an equation of this form.
The paper deals with an evolutionary integro-differential equation describing nonlinear waves. Particular choice of the kernel in the integral leads to well-known equations such as the Khokhlov-Zabolotskaya equation, the Kadomtsev-Petviashvili equation and others. Since solutions of these equations describe many physical phenomena, analysis of the general model studied in the paper equation is important. One of the methods for obtaining solutions differential equations is provided by the Lie group analysis. However, this method is not applicable to integro-differential equations. Therefore we discuss new approaches developed in modern group analysis and apply them to the general model considered in the present paper. Reduced equations and exact solutions are also presented.
A general methodology for linearization of fourth order ordinary differential equations is developed using point transformations. The solution of the problem on linearization of fourth-order equations by means of point transformations is presented here. We show that all fourth-order equations that are linearizable by point transformations are contained in the class of equations which is linear in the third-order derivative. We provide the linearization test and describe the procedure for obtaining the linearizing transformations as well as the linearized equation. For ordinary differential equations of order greater than 4 we obtain necessary conditions, which separate all linearizable equations into two classes.
We present here the solution of the problem on linearization of fourth-order equations by means of point transformations. We show that all fourth-order equations that are linearizable by point transformations are contained in the class of equations which is linear in the third-order derivative. We provide the linearization test and describe the procedure for obtaining the linearizing transformations as well as the linearized equation.
The paper is dedicated to construction of invariants for the parabolic equation u(t) + a(t, x)u(xx) + b(t, x)u(x) + c(t, x)u = 0. We consider the equivalence group given by point transformations and find all invariants up to seventh-order, i.e. the invariants involving the derivatives up to seventh-order of the coefficients a, b and c with respect to the independent variables t, x. (c) 2006 Elsevier B.V. All rights reserved.
The principle of an a priori use of symmetries is proposed as a new approach to solving nonlinear problems on the basis of a reasonable complication of mathematical models. This approach often provides additional symmetries, and hence opens possibilities to find new analytical solutions. The potentialities of the proposed approach are illustrated by applying to problems of nonlinear acoustics.
We consider evolution equations of the form ut = f(x, u, ux)uxx + g(x, u, ux) and ut = uxx + g(x, u, ux). In the spirit of the recent work of Ibragimov [Ibragimov NH. Laplace type invariants for parabolic equations. Nonlinear Dynam 2002;28:125-33] who adopted the infinitesimal method for calculating invariants of families of differential equations using the equivalence groups, we apply the method to these equations. We show that the first class admits one differential invariant of order two, while the second class admits three functional independent differential invariants of order three. We use these invariants to determine equations that can be transformed into the linear diffusion equation.
Most of mathematical models describing spread of malignant tumours are formulated as systems of nonlinear partial differential equations containing, in general, several unknown functions of dependent variables. Determination of these unknown functions (called in group analysis arbitrary elements) is a complicated problem that challenges researchers. Our aim is to calculate the generators of the equivalence group for one of the known models and, using the equivalence generators, specify arbitrary elements, find additional symmetries and calculate group invariant solutions.
We show numerically that vector antenna arrays can generate radio beams that exhibit spin and orbital angular momentum characteristics similar to those of helical Laguerre-Gauss laser beams in paraxial optics. For low frequencies (1 GHz), digital techniques can be used to coherently measure the instantaneous, local field vectors and to manipulate them in software. This enables new types of experiments that go beyond what is possible in optics. It allows information-rich radio astronomy and paves the way for novel wireless communication concepts.
In this paper we generalize the classification of self-adjoint second-order linear partial differential equation to a family of nonlinear wave equations with two independent variables. We find a class of quasi self-adjoint nonlinear equations which includes the self-adjoint linear equations as a particular case. The property of a differential equation to be quasi self-adjoint is important, e.g. for constructing conservation laws associated with symmetries of the differential equation.
A (2 + 1)-dimensional generalized Burgers equation is considered. Having written this equation as a system of two dependent variables, we show that it is quasi self-adjoint and find a nontrivial additional conservation law.
We apply the infinitesimal technique for calculating invariants for the family of nonlinear equations formulated in the title. We show that the infinite-dimensional equivalence Lie algebra has three functionally independent differential invariants of the second order. Knowledge of invariants of families of equations is essential for identifying distinctly different equations and therefore for the problem of group classification.
A general theorem on symmetries and conservation laws is applied to gasdynamic equations considered together with the adjoint equations. In particular, new non-local conservation laws for the polytropic gas are obtained.
We apply the general theorem on symmetries and conservation laws proved recently by N.H. Ibragimov to gasdynamic equations considered together with the adjoint equations. In particular, we derive conservation laws for the polytropic gas.
Determining equations for approximate symmetries of Ito and Stratonovich dynamical systems is obtained. It is shown that approximate conservation laws can be found from the approximate symmetries of stochastic dynamical systems which do not arise from a Hamiltonian.
Approximate symmetries and conservation laws for deterministic and stochastic differential equations with a small parameter are discussed in detail. Determining equations for infinitesimal approximate symmetries of Ito and Stratanovich dynamical systems are derived. It is shown how to derive conserved quantities for stochastic dynamical systems using their approximate symmetries without recourse to Noether's theorem
In the present paper a quantum drift–diffusion model describing semi-conductor devices is considered. New conservation laws for the model are computed and used to construct exact solutions.
This book contains 33 papers presented at the 10th International conference "Modern Group Analysis" held in Larnaca, Cyprus, during 24-31 October 2004. All papers have been reviewed by two independent referees.
The Resonant Triad Model (RTM) developed in (Ibragimov, 2007), is used to study the Thorpe’s problem (Thorpe, 1997) on the existence of self-resonant internal waves, i.e., the waves for which a resonant interaction occurs at second order between the incident and reflected internal waves off slopes. The RTM represents the extension of the McComas and Bretherton’s three wave hydrostatic model (McComas and Bretherton, 1977) which ignores the effects of the earth’s rotation to the case of the non-hydrostatic analytical model involving arbitrarily large number of rotating internal waves with frequencies spanning the range of possible frequencies, i.e., between the maximum of the buoyancy frequency (vertical motion) and a minimum of the inertial frequency (horizontal motion). The present analysis is based on classification of resonant interactions into the sum, middle and difference interaction classes. It is shown in this paper that there exists a certain value of latitude, which is classified as the singular latitude, at which the coalescence of the middle and difference interaction classes occurs. Such coalescence, which apparently had passed unnoticed before, can be used to study the Thorpe’s problem on the existence of selfresonant waves. In particular, it is shown that the value of the bottom slope at which the second-order frequency and wave number components of the incident and reflected waves satisfy the internal wave dispersion relation can be approximated by two latitude-dependent parameters in the limiting case when latitude approaches its singular value. Since the existence of a such singular latitude is generic for resonant triad interactions, a question on application of the RTM to the modeling of enhanced mixing in the vicinity of ridges in the ocean arises.
The research report is focused on optimization algorithms with application to quality of service (QoS) routing. A brief theoretical background is provided for mathematical tools in relation to optimization theory. The rest of the report provides a survey of different types of optimization algorithms: several numerical methods, a heuristics and a metaheuristic. In particular, we discuss basic descent methods, gradient-based methods, particle swarm optimization (PSO) and a constrained-path selection algorithm called Self-Adaptive Multiple Constraints Routing Algorithm (SAMCRA).
The uplink load for the scheduling of Enhanced-Uplink (E-UL) channels determine the achievable data rate for Wideband Code Division Multiple Access (WCDMA) systems, therefore its accurate measurement carries a prime significance. The uplink load also known as Rise-over-Thermal (RoT), which is the quotient of the Received Total Wideband Power (RTWP) and the Thermal Noise Power floor. It is a major parameter which is calculated at each Transmission Time Interval (TTI) for maintaining cell coverage and stability. The RoT algorithm for evaluation of uplink load is considered as a complex and resource demanding among several Radio Resource Management (RRM) algorithms running in a radio system. The main focus of this thesis is to study RoT algorithm presently deployed in radio units and its possible optimization by reducing complexity of the algorithm in terms of memory usage and processing power. The calculation of RoT comprises three main blocks a Kalman filter, a noise floor estimator and the RoT computation. After analyzing the complexity of each block it has been established that the noise floor estimator block is consuming most of the processing power producing peak processor load since it involves many complex floating point calculations. However, the other blocks do not affect the processing load significantly. It was also observed that some block updates can be reduced in order to decrease the average load on the processor. Three techniques are proposed for reducing the complexity of the RoT algorithm, two for the reduction of peak load and one for the reduction of average load. For reducing the peak load, an interpolation approach is used instead of performing transcendental mathematical calculations. Also, the calculations involving noise floor estimation are extended over several TTIs by keeping in view that the estimation is not time critical. For the reduction of average load, the update rate for the Kalman Filter block is reduced. Based on these optimization steps, a modified algorithm for RoT computation with reduced complexity is proposed. The proposed changes are tested by means of MATLAB simulations demonstrating the improved performance with consistency in the output results. Finally, an arithmetic operation count is done using the hardware manual of Power PC (PPC405) used in Platform 4, which gives a rough estimate of decrease in the percentage of calculations after optimization.
We are living in a world full of uncertainty and ambiguity. We usually ask ourselves questions that we are uncertain about their answers. Is it going to rain tomorrow? What will be the exchange rate of euro next month? Why, where and how should I invest? Type-1 Fuzzy sets are characterized by the membership function whose value for a given element x is said to be the grade of membership having a value in the interval [0, 1]. In addition, type-1 fuzzy sets have limited capabilities to deal with uncertainty. In our thesis, we study another concept of a fuzzy description of uncertainty which is called Type-2 fuzzy sets. According to this concept, for any given element x, we can’t speak of an unambiguously specified value of the membership function. Moreover, Type-2 fuzzy sets constitute a powerful tool for handling uncertainty. The aim of our thesis is to examine the potential of the Type-2 fuzzy sets especially in decision making. So, we present basic definitions concerning Type-2 fuzzy sets, and operations on these sets are to be discussed too. Then, Type-2 fuzzy relations and methods of transformation of Type-2 fuzzy sets will be introduced. Also, the theory of Type-2 Fuzzy sets will serve for the construction of the fuzzy inference system. Finally, we utilize interval type-2 fuzzy sets in the application of Multiple Attributes Group Decision Making which is called TOPSIS.
The global Internet has seen tremendous growth in terms of nodes and user base as well as of types of applications. One of the most important consequences of this growth is related to an increased complexity of the traffic experienced in these networks. Each application has a set of unique characteristics in terms of performance characteristics, transactions as well as the way the transaction processing profile maps onto unique network resource requirements. In order to support Internet applications effectively,it is therefore important to understand and to characterize the application level transactions as well as the effect of different TCP/IP control mechanisms on application-level parameters. It is the goal of this paper to model and to evaluate the characteristics of World Wide Web traffic. Results are reported on measuring, modeling and analysis of specific Hyper Text Transfer Protocol traffic collected from different (classes of) sites together with methodologies used for capturing HTTP flows as well as for modeling. The paper concludes with a discussion on the structure of Web pages and a model for the generation of the number of embedded pages in a Web page is suggested.
Based on symmetry and invariance principles, Lie group analysis is the only systematic method for solving nonlinear differential equations analytically. Nonlinear second-order ordinary differential equations admitting two-dimensional Lie algebras can be transformed into one of the four types of canonical forms via Lie's integration method. In this thesis, Lie's second-order equation of type III is considered from the point of view of equivalence transformations. The generators of the equivalence group and the principal Lie algebra are calculated.
This thesis comprises investigation of the mathematical model of acoustic waves in a fluid with bubbles for nonlinear self-adjointness, Lie point symmetries, conservation laws and invariant solutions. It is based on the theory developed recently by Prof. Nail Ibragimov. It is shown that the systems of differential equations describing the model are nonlinearly self-adjoint. The symmetries are calculated and the conservation laws are constructed using the formal Lagrangian. In addition, invariant solutions are derived.
The Objective of this thesis is to talk about the usage of Fuzzy Logic in pattern recognition. There are different fuzzy approaches to recognize the pattern and the structure in data. The fuzzy approach that we choose to process the data is completely depends on the type of data. Pattern reorganization as we know involves various mathematical transforms so as to render the pattern or structure with the desired properties such as the identification of a probabilistic model which provides the explaination of the process generating the data clarity seen and so on and so forth. With this basic school of thought we plunge into the world of Fuzzy Logic for the process of pattern recognition. Fuzzy Logic like any other mathematical field has its own set of principles, types, representations, usage so on and so forth. Hence our job primarily would focus to venture the ways in which Fuzzy Logic is applied to pattern recognition and knowledge of the results. That is what will be said in topics to follow. Pattern recognition is the collection of all approaches that understand, represent and process the data as segments and features by using fuzzy sets. The representation and processing depend on the selected fuzzy technique and on the problem to be solved. In the broadest sense, pattern recognition is any form of information processing for which both the input and output are different kind of data, medical records, aerial photos, market trends, library catalogs, galactic positions, fingerprints, psychological profiles, cash flows, chemical constituents, demographic features, stock options, military decisions.. Most pattern recognition techniques involve treating the data as a variable and applying standard processing techniques to it.
A recent theorem on nonlocal conservation laws is applied to a magma equation modelling a melt migration through the Earth´s mantle. It is shown that the equation in question is quasi-self-adjoint. The self-adjoint equations are singled out. Nonlocal and local conservation densities are obtained using the symmetries of the magma equation.
Conservation laws play an important role in science. The aim of this thesis is to provide an overview and develop new methods for constructing conservation laws using Lie group theory. The derivation of conservation laws for invariant variational problems is based on Noether’s theorem. It is shown that the use of Lie-Bäcklund transformation groups allows one to reduce the number of basic conserved quantities for differential equations obtained by Noether’s theorem and construct a basis of conservation laws. Several examples on constructing a basis for some well-known equations are provided. Moreover, this approach allows one to obtain new conservation laws even for equations without Lagrangians. A formal Lagrangian can be introduced and used for computing nonlocal conservation laws. For self-adjoint or quasi-self-adjoint equations nonlocal conservation laws can be transformed into local conservation laws. One of the fields of applications of this approach is electromagnetic theory, namely, nonlocal conservation laws are obtained for the generalized Maxwell-Dirac equations. The theory is also applied to the nonlinear magma equation and its nonlocal conservation laws are computed.
In this paper the general magma equation modelling a melt flow in the Earth's mantle is discussed. Applying the new theorem on nonlocal conservation laws [Ibragimov NH. A new conservation theorem. J Math Anal Appl 2007;333(1):311-28] and using the symmetries of the model equation nonlocal conservation laws are computed. In accordance with Ibragimov [Ibragimov NH. Quasi-self-adjoint differential equations. Preprint in Archives of ALGA, vol. 4, BTH, Karlskrona, Sweden: Alga Publications; 2007. p. 55-60, ISSN: 1652-4934] it is shown that the general magma equation is quasi-self-adjoint for arbitrary m and n and self-adjoint for n = -m. These important properties are used for deriving local conservation laws. © 2008 Elsevier B.V. All rights reserved.
Clusters and distributed systems offer fault tolerance and high performance through load sharing. When all n computers are up and running, we would like the load to be evenly distributed among the computers. When one or more computers break down, the load on these computers must be redistributed to other computers in the system. The redistribution is determined by the recovery scheme. The recovery scheme is governed by a sequence of integers modulo n. Each sequence guarantees minimal load on the computer that has maximal load even when the most unfavorable combinations of computers go down. We calculate the best possible such recovery schemes for any number of crashed computers by an exhaustive search, where brute force testing is avoided by a mathematical reformulation of the problem and a branch-and-bound algorithm. The search nevertheless has a high complexity. Optimal sequences, and thus a corresponding optimal bound, are presented for a maximum of twenty one computers in the distributed system or cluster.
Consider a parallel program with n processes and a synchronization granularity z. Consider also two parallel architectures: an SMP with q processors and run-time reallocation of processes to processors, and a distributed system (or cluster) with k processors and no run-time reallocation. There is an inter-processor communication delay of t time units for the system with no run-time reallocation. In this paper we define a function H(n,k,q,t,z) such that the minimum completion time for all programs with n processes and a granularity z is at most H(n,k,q,t,z) times longer using the system with no reallocation and k processors compared to using the system with q processors and run-time reallocation. We assume optimal allocation and scheduling of processes to processors. The function H(n,k,q,t,z)is optimal in the sense that there is at least one program, with n processes and a granularity z, such that the ratio is exactly H(n,k,q,t,z). We also validate our results using measurements on distributed and multiprocessor Sun/Solaris environments. The function H(n,k,q,t,z) provides important insights regarding the performance implications of the fundamental design decision of whether to allow run-time reallocation of processes or not. These insights can be used when doing the proper cost/benefit trade-offs when designing parallel execution platforms.
Clusters and distributed systems offer fault tolerance and high performance through load sharing. When all computers are up and running, we would like the load to be evenly distributed among the computers. When one or more computers break down the load on these computers must be redistributed to other computers in the cluster. The redistribution is determined by the recovery scheme. The recovery scheme should keep the load as evenly distributed as possible even when the most unfavorable combinations of computers break down, i.e. we want to optimize the worst-case behavior. We have previously defined recovery schemes that are optimal for some limited cases. In this paper we find a new recovery schemes that are based on so called Golomb rulers. They are optimal for a much larger number of cases than the previous results.
"Communications in Nonlinear Science and Numerical Simulation'' is given entirely to appreciation of applications of Lie groups to nonlinear problems in acoustics, engineering, biomedicine, etc. The selection of papers covers the following topics: a) group classification of differential equations and optimal systems of invariant and partially invariant solutions including classification of differential equations according to their symmetries; b) equivalence groups and invariants of families of differential equations; c) symmetries of delay equations; d) symmetries of stochastic differential equations; e) application to nonlinear physics and biomathematics. We hope that this special issue highlights the recent major developments in this fascinating field of mathematics and mathematical modelling.
The increased occurrence of railway traffic disturbances shows that effective re-scheduling is important. In previous research we have designed an optimization-based approach which seems promising. However, for some scenarios it is difficult to find good solutions within seconds. Therefore, we have developed a greedy algorithm which effectively delivers good solutions within the permitted time. To quickly retrieve a feasible solution the algorithm performs a depth-first search using an evaluation function to prioritise when conflicts arise and then branches according to a set of criteria.
The positive trend of increased use of railway transportation in Europe has resulted in an increased sensitivity to and occurrence of traffic disturbances. In addition to the need for extensions of the infrastructure, the need to effectively limit and predict the effects of disturbances becomes apparent. The kernel of the disturbance management problem is to revise the original timetable in line with the new conditions and decide where, when and how trains should overtake or meet to minimise the negative effect of the disturbance. In previous research, the author has designed optimisation-based approach for rescheduling, which seems promising, but for some scenarios it is difficult to find good solutions within seconds. Also, more detailed constraints will have to be included, which makes the problem even more complex and difficult to solve. Therefore the author developed a greedy algorithm that effectively delivers good solutions within the permitted time. To quickly retrieve a feasible solution, the algorithm performs a depth-first search using an evaluation function to prioritise when conflicts arise and then branches according to a set of criteria. A performance analysis of the algorithm was carried out using simulated experiments showing its strengths and weaknesses.
Combinatorial optimization is a diverse area of mathematics. It concerns optimization on feasible regions defined by discrete sets, graphs, hypergraphs, matroids, etc. . . which all have a large number of applications. They occur in virtually all domains of human activity since humans always want to do things easier, faster, consume less resources, etc. . . This thesis concerns three applied problems within combinatorial optimization. The first paper generalizes previous optimal upper bounds on the minimum Euclidean distance for phase-shift keying (PSK) block codes, that are explicit in the parameters alphabet size, block length and code size. There is a strong connection between high minimum Euclidean distance and good error-correcting capabilities. The bounds are generalized in several respects, such as from codes on symmetric PSK to codes on asymmetric PSK. They are also generalized to other types of noise than Gaussian, allowing more efficient block codes when noise is non-Gaussian. We provide examples of codes on asymmetric PSK that have higher minimum Euclidean distance than any comparable codes on symmetric PSK.Several classes of codes are shown to be optimal among codes on symmetric PSK since their Euclidean distance coincides with the bound. The second paper considers a parallel computer system with m identical computers,where we study optimal performance precaution for one possible computer crash. We anticipate that some computer may crash, and restrict the cost in such a situation. How costly is such a precaution when no crash occurs? We set a restriction that the completion time of a parallel program after a crash is at most a factor r + 1 larger than if we use an optimal allocation with m - 1 computers. This is an r-dependent restriction of the set of allocations of a program. Then the worst-case ratio of the optimal r-dependent completion time in the case of no crash and the unrestricted optimal completion time defines a function f(r,m). In the paper we establish upper and lower bounds of the worst-case cost function f(r,m) and characterize worst-case programs. The third paper considers the problem of Map Matching (MM), i.e. matching time and location measurements of a vehicle to a route in a road network. The paper presents a probabilistic algorithm for MM based on a second order hidden Markov model (HMM), as opposed to first order HMMs which are usually used. This allows a more detailed analysis of the data while preserving algorithmic complexity O(n). Both measurement densities and transition probabilities are determined with respect to Kolmogorov's third axiom, which in this context implies that the probabilities are additive over a partition of a road segment.
This paper generalizes previous optimal upper bounds on the minimum Euclidean distance for phase shift keying (PSK) block codes, that are explicit in three parameters: alphabet size, block length and code size. The bounds are primarily generalized from codes over symmetric PSK to codes over asymmetric PSK and also to general alphabet size. Furthermore, block codes are optimized in the presence of other types of noise than Gaussian, which induces also non-Euclidean distance measures. In some instances, codes over asymmetric PSK prove to give higher Euclidean distance than any code over symmetric PSK with the same parameters. We also provide certain classes of codes that are optimal among codes over symmetric PSK.
The minimum Euclidean distance is a fundamental quantity for block coded phase shift keying (PSK). In this paper we improve the bounds for this quantity that are explicit functions of the alphabet size q, block length n and code size | C |. For q = 8, we improve previous results by introducing a general inner distance measure allowing different shapes of a neighborhood for a codeword. By optimizing the parameters of this inner distance measure, we find sharper bounds for the outer distance measure, which is Euclidean. The proof is built upon the Elias critical sphere argument, which localizes the optimization problem to one neighborhood. We remark that any code with q = 8 that fulfills the bound with equality is best possible in terms of the minimum Euclidean distance, for given parameters n and | C |. This is true for many multilevel codes.
We consider energy minimization by speed-scaling of an open shop multiprocessor with n jobs and m machines. The paper studies the complexity of a primal-dual solution algorithm of [4], which was an open question in that paper.We prove that in a neighbourhood of the solution the complexity of the algorithm is O(mn log(1/ε) if n and m are not equal and ε is the roundoff error of the computer. The paper demonstrates how linearization can be used to investigate the complexity of an algorithm close to the optimum. An estimate of the size of the neighbourhood where the linearization error is smaller than the computer’s roundoff error is also given.
A logical graph is a certain directed graph with which any mathematical theory or proof can be presented - its logic is formulated in graph form. Compared to the usual narrative description, the presentation usually gains in survey, clarity and precision. A logical graph formulation can be thought of as a detailed and complete map over the mathematical landscape. The main goal in the design of logical graphs is didactical: to improve the orientation in a mathematical proof or theory for a reader, and thus to improve the access of mathematics.
The n-dimensional Stern-Brocot tree consists of all sequences (p₁, ...,p_{n}) of positive integers with no common multiple. The relatively prime sequences can be generated branchwise from each other by simple vector summation, starting with an ON-base, and controlled by a generalized Euclidean algorithm.The tree induces a multiresolution partition of the first quadrant of the (n-1)-dimensional unit sphere, providing a direction approximation property of a sequence by its ancestors. Two matrix representations are introduced, where in both a matrix contains the parents of a sequence. From one of them the isomorphism of a subtree to the entire tree of dimension equal to the number of parents of the top sequence follows. A form of Fibonacci sequences turn out to be the sequences of fastest growing sums. The construction can be regarded an n-dimensional continued fraction, and it may invite further n-dimesional number theory.
Consider a multiprocessor with $k$ identical processors, executing parallel programs consisting of $n$ processes. Let $T_s(P)$ and $T_d(P)$ denote the execution times for the program $P$ with optimal static and dynamic allocations respectively, i. e. allocations giving minimal execution time. We derive a general and explicit formula for the maximal execution time ratio $g(n,k)=\max T_s(P)/T_d(P)$, where the maximum is taken over all programs $P$ consisting of $n$ processes. Any interprocess dependency structure for the programs $P$ is allowed, only avoiding deadlock. Overhead for synchronization and reallocation is neglected. Basic properties of the function $g(n,k)$ are established, from which we obtain a global description of the function. Plots of $g(n,k)$ are included. The results are obtained by investigating a mathematical formulation. The mathematical tools involved are essentially tools of elementary combinatorics. The formula is a combinatorial function applied on certain extremal matrices corresponding to extremal programs. It is mathematically complicated but rapidly computed for reasonable $n$ and $k$, in contrast to the np-completeness of the problems of finding optimal allocations.