Solving Linear Systems Whose Elements Are Nonlinear Functions of Intervals

The paper addresses the problem of solving linear algebraic systems the elements of which are, in the general case, nonlinear functions of a given set of independent parameters taking on their values within prescribed intervals. Three kinds of solutions are considered: (i) outer solution, (ii) interval hull solution, and (iii) inner solution. A simple direct method for computing a tight outer solution to such systems is suggested. It reduces, essentially, to inverting a real matrix and solving a system of real linear equations whose size n is the size of the original system. The interval hull solution (which is a NP-hard problem) can be easily determined if certain monotonicity conditions are fulfilled. The resulting method involves solving n+1 interval outer solution problems as well as 2n real linear systems of size n. A simple iterative method for computing an inner solution is also given. A numerical example illustrating the applicability of the methods suggested is solved.     

Efficient spectral ultraspherical-Galerkin algorithms for the direct solution of 2nth-order linear differential equations

Some efficient and accurate algorithms based on the ultraspherical-Galerkin method are developed and implemented for solving 2nth-order linear differential equations in one variable subject to homogeneous and nonhomogeneous boundary conditions using a spectral discretization. We extend the proposed algorithms to solve the two-dimensional 2nth-order differential equations. The key to the efficiency of these algorithms is to construct appropriate base functions, which lead to linear systems with specially structured matrices that can be efficiently inverted, hence greatly reducing the cost and roundoff errors.     

Reliability analysis of k-out-of-n: F balanced systems with multiple functional sectors

In this paper, new concepts of balanced systems are proposed based on real engineering problems. The system under study consists of l groups and each group has n functional sectors. The conception of balance difference is proposed for the first time. It is assumed that unbalanced systems are rebalanced by either forcing down some working units into standby or resuming some standby units into operation. In addition, a case that the forced-down units are subject to failure during standby is studied in this paper. Based on different balanced cases and system failure criteria, two reliability models for balanced systems are developed. The proposed systems have widespread applications in aerospace and military industries, such as wing systems of airplane and unmanned aerial vehicles with balanced engine systems. Markov process imbedding method is used to analyze the number of working units in each sector for each model. Finite Markov chain imbedding approach and universal generating function technique are used to obtain the system reliability for different models. Several case studies are finally presented to demonstrate the new models.     

Existence and the optimal choice of the values of parameters in inequalities guaranteeing the validity of embedding theorems

For systems of linear algebraic equations with matrix of coefficientsa _ij (i,j=1...,n where under certain assumptions regarding the form of the matrix and for nonnegative right-hand sides, one establishes necessary and sufficient conditions for the existence of strictly positive solutions. One considers applications in the imbedding theory of functional spaces.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 111, pp. 63–87, 1981.     

Dual imbeddings and wrapped quasi-coverings of graphs

This paper gives a new method for constructing imbeddings of graphs which are “nearly” coverings of given imbedded graphs. The method is based on the dual theories of current graphs and voltage graphs. Some applications are given, in particular the following theorem: Let G be any graph which has a triangular imbedding in the sphere. Then there are infinitely many integers n for which the composition G[nK₁] has a triangular (orientable surface) imbedding.     

Remarks on integrable systems

The problem of integrability conditions for systems of differential equations is discussed. Darboux’s classical results on the integrability of linear non-autonomous systems with an incomplete set of particular solutions are generalized. Special attention is paid to linear Hamiltonian systems. The paper discusses the general problem of integrability of the systems of autonomous differential equations in an n-dimensional space, which admit the algebra of symmetry fields of dimension ? n. Using a method due to Liouville, this problem is reduced to investigating the integrability conditions for Hamiltonian systems with Hamiltonians linear in the momenta in phase space of dimension that is twice as large. In conclusion, the integrability of an autonomous system in three-dimensional space with two independent non-trivial symmetry fields is proved. It should be emphasized that no additional conditions are imposed on these fields.     

Linear differential equations and multiple zeta values. II. A generalization of the WKB method

For linear differential equations x(n)+a₁x(n−1)+?+anx=0 (and corresponding linear differential systems) with large complex parameter λ and meromorphic coefficients aj=aj(t;λ) we prove existence of analogues of Stokes matrices for the asymptotic WKB solutions. These matrices may depend on the parameter, but under some natural assumptions such dependence does not take place. We also discuss a generalization of the Hukuhara-Levelt-Turritin theorem about formal reduction of a linear differential system near an irregular singular point t=0 to a normal form with ramified change of time to the case of systems with large parameter. These results are applied to some hypergeometric equations related with generating functions for multiple zeta values.     

An efficient fourth order weighted-Newton method for systems of nonlinear equations

In this paper, we develop a fourth order method for solving the systems of nonlinear equations. The algorithm is composed of two weighted-Newton steps and requires the information of one function and two first Fréchet derivatives. Therefore, for a system of n equations, per iteration it uses n?+?2n ² evaluations. Computational efficiency is compared with Newton’s method and some other recently published methods. Numerical tests are performed, which confirm the theoretical results. From the comparison with known methods it is observed that present method shows good stability and robustness.     

Exact slow-fast decomposition of the singularly perturbed matrix differential Riccati equation

In this paper the Hamiltonian matrix formulation of the Riccati equation is used to derive the reduced-order pure-slow and pure-fast matrix differential Riccati equations of singularly perturbed systems. These pure-slow and pure-fast matrix differential Riccati equations are obtained by decoupling the singularly perturbed matrix differential Riccati equation of dimension n₁+n₂ into the pure-slow regular matrix differential Riccati equation of dimension n₁ and the pure-fast stiff matrix differential Riccati equation of dimension n₂. A formula is derived that produces the solution of the original singularly perturbed matrix differential Riccati equation in terms of solutions of the pure-slow and pure-fast reduced-order matrix differential Riccati equations and solutions of two reduced-order initial value problems. In addition to its theoretical importance, the main result of this paper can also be used to implement optimal filtering and control schemes for singularly perturbed linear time-invariant systems independently in pure-slow and pure-fast time scales.     

Multivariate exponential analysis from the minimal number of samples

The problem of multivariate exponential analysis or sparse interpolation has received a lot of attention, especially with respect to the number of samples required to solve it unambiguously. In this paper we show how to bring the number of samples down to the absolute minimum of (d +?1)n where d is the dimension of the problem and n is the number of exponential terms. To this end we present a fundamentally different approach for the multivariate problem statement. We combine a one-dimensional exponential analysis method such as ESPRIT, MUSIC, the matrix pencil or any Prony-like method, with some linear systems of equations because the multivariate exponents are inner products and thus linear expressions in the parameters.     

A stable approach to Newton's method for general mathematical programming problems inR n

The usual approach to Newton's method for mathematical programming problems with equality constraints leads to the solution of linear systems ofn +m equations inn +m unknowns, wheren is the dimension of the space andm is the number of constraints. Moreover, these linear systems are never positive definite. It is our feeling that this approach is somewhat artificial, since in the unconstrained case the linear systems are very often positive definite. With this in mind, we present an alternate Newton-like approach for the constrained problem in which all the linear systems are of order less than or equal ton. Furthermore, when the Hessian of the Lagrangian at the solution is positive definite (a situation frequently occurring), all our systems will be positive definite. Hence, in all cases, our Newton-like method offers greater numerical stability. We demonstrate that the convergence properties of this Newton-like method are superior to those of the standard approach to Newton's method. The operation count for the new method using Gaussian elimination is of the same order as the operation count for the standard method. However, if the Hessian of the Lagrangian at the solution is positive definite and we use Cholesky decomposition, then the order of the operation count for the new method is half that for the standard approach to Newton's method. This theory is generalized to problems with both equality and inequality constraints.     

Solution to fuzzy system of linear equations with crisp coefficients

This paper presents a new and simple method to solve fuzzy real system of linear equations by solving two n × n crisp systems of linear equations. In an original system, the coefficient matrix is considered as real crisp, whereas an unknown variable vector and right hand side vector are considered as fuzzy. The general system is initially solved by adding and subtracting the left and right bounds of the vectors respectively. Then obtained solutions are used to get a final solution of the original system. The proposed method is used to solve five example problems. The results obtained are also compared with the known solutions and found to be in good agreement with them.     

Linear equations and interpolation in Boolean algebra

The authors generalize the classical interpolation formula for Boolean functions of n variables. A characterization of all interpolating systems with 2ⁿ elements is obtained. The methods of proof used are intimately related to the solution of linear Boolean equations.     

On the equivalence of linear equations under nonlocal transformation

Linear nth order (n?3) ordinary differential equations have been shown to possess n+1, n+2 or n+4 Lie point symmetries. Each class contains equations which are equivalent under point transformation. By taking the example of third order equations, we show that all linear equations are equivalent if the class of transformation is broadened to include nonlocal transformations and hence the representative of this class of equations is y⁽ⁿ⁾=0.     

A new Carleman inequality for parabolic systems with a single observation and applications

In this Note, we present Carleman estimates for linear reaction–diffusion–convection systems of two equations and linear reaction–diffusion systems of three equations. These estimates are the key for proving controllability results for semilinear reaction–diffusion–convection systems of order 2 and reaction–diffusion systems of order 3. They allow us to derive results for identification of n coefficients by $(n?2)$ observations.     

Upper bounds on the complexity of solving systems of linear equations

The article is of the nature of a survey and is devoted to direct (exact) methods of solving systems of linear equations examined from the point of view of their computational complexity. The construction of most of the algorithms is outlined. The paper consists of two parts. Series methods of solving systems of linear equations are examined in the first part. It includes the algorithms of Gauss and of Konoval'tsev, Strassen's algorithm and its modifications, the YunGustavson results for Toeplitz systems, etc. The second part is devoted to parallel methods of solving systems of linear equations. Examined here are the parallelization of the Gauss algorithm, the results of Hyafil and Kung on complexity estimate of the parallel solution of triangular systems, Csanky's results based on the parallelization of Leverrier's method, Hyabil's general result on the parallelization of a straight-line program for computing polynomials, Stone's algorithm for the parallel solving of tridiagonal systems. Several new bounds are derived. In particular, if a pair of (n×n) -matrices can be multiplied sequentially by a straight-line program of complexity O(n^d), then it is possible to solve an arbitrary system of m linear equations in n unknowns on p processors with the complexity $$0\left( {\frac{{max(m, n)min(m, n)^{\alpha - 1} }}{p} + min(m, n)log_2 max(m, n)} \right),$$ , and to solve a triangular system of sizen with the complexity $$0\left( {\frac{{n^2 }}{p} + \frac{n}{{p^{1/\alpha } }}log_2^{1 - \tfrac{1}{\alpha }} n + log_2^2 n} \right).$$      

Finite dimensional imbeddings of harmonic spaces

For a noncompact harmonic manifoldM we establish finite dimensionality of the eigensubspacesV _γ generated by radial eigenfunctions of the form coshr+c. As a consequence, for such harmonic manifolds, we give an isometric imbedding ofM into (V _γ,B), whereB is a nondegenerate symmetric bilinear indefinite form onV _γ (analogous to the imbedding of the real hyperbolic spaceH ⁿ into ? ⁿ⁺¹ with the indefinite formQ(x,x)=?x ₀ ² +Σx _i ² ). This imbedding is minimal in a ‘sphere’ in (V _γ,B). Finally we give certain conditions under whichM is symmetric.     

On CCZ-equivalence of addition mod 2 n

We show that addition mod 2 ⁿ is CCZ-equivalent to a quadratic vectorial Boolean function. We use this to reduce the solution of systems of differential equations of addition to the solution of an equivalent system of linear equations and to derive a fully explicit formula for the correlation coefficients, which leads to enhanced results about the Walsh transform of addition mod 2 ⁿ . The results have direct applications in the cryptanalysis of cryptographic primitives which use addition mod 2 ⁿ .     

Convergent series solution of nonlinear equations

The author's decomposition method [1] provides a new, efficient computational procedure for solving large classes of nonlinear (and/or stochastic) equations. These include differential equations containing polynomial, exponential, and trigonometric terms, negative or irrational powers, and product nonlinearities [2]. Also included are partial differential equations [3], delay-differential equations [4], algebraic equations [5], and matrix equations [6] which describe physical systems. Essentially the method provides a systematic computational procedure for equations containing any nonlinear terms of physical significance. The procedure depends on calculation of the author's A_n, a finite set of polynomials [1,13] in terms of which the nonlinearities can be expressed. This paper shows important properties of the A_n which ensure an accurate and computable convergent solution by the author's decomposition method [1]. Since the nonlinearities and/or stochasticity which can be handled are quite general, the results are potentially extremely useful for applications and make a number of common approximations such as linearization, unnecessary.