Direct and iterative methods for interval parametric algebraic systems producing parametric solutions

This paper deals with interval parametric linear systems with general dependencies. Motivated by the so‐called parameterized solution introduced by Kolev, we consider the enclosures of the solution set in a revised affine form. This form is advantageous to a classical interval solution because it enables us to obtain both outer and inner bounds for the parametric solution set and, thus, intervals containing the endpoints of the hull solution, among others. We propose two solution methods, a direct method called the generalized expansion method and an iterative method based on interval‐affine Krawczyk iterations. For the iterative method, we discuss its convergence and show the respective sufficient criterion. For both methods, we perform theoretical and numerical comparisons with some other approaches. The numerical experiments, including also interval parametric linear systems arising in practical problems of structural and electrical engineering, indicate the great usefulness of the proposed methodology and its superiority over most of the existing approaches to solving interval parametric linear systems.     

Generalization of a Parametric Fixed‐Point Iteration

Based on new sufficient regularity conditions, Rump's method for solving parametric interval linear systems is generalized which expands its scope of applicability over a class of co‐called column‐dependent parametric matrices. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Inner and outer bounds for the solution set of parametric linear systems

Consider linear systems involving affine-linear dependencies on interval parameters. Presented is a free C-XSC software implementing a generalized parametric fixed-point iteration method for verified enclosure of the parametric solution set. Some specific features of the corresponding algorithm concerning sharp enclosure of the contracting matrix and inner approximation of the solution enclosure are discussed.     

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.     

Using Interval Arithmetic for Determining the Structure of Convex Hulls

We discuss the use of interval arithmetic in the computation of the convex hull of n points in D dimensions. Convex hull algorithms rely on simple geometric tests, such as “does some point p lie in a certain half-space or affine subspace?” to determine the structure of the hull. These tests in turn can be carried out by solving appropriate (not necessarily square) linear systems. If interval-based methods are used for the solution of these systems then the correct hull can be obtained at lower cost than with exact arithmetic. In addition, interval-based methods can determine the topological structure of the convex hull even if the position of the points is not known exactly. In the present paper we compare various interval linear solvers with respect to their ability to handle close-to-pathological situations. This property determines how often interval arithmetic cannot provide the required information and therefore some computations must be redone with exact arithmetic.     

A new algorithm for Chebyshev minimum-error multiplication of reduced affine forms

Reduced affine arithmetic (RAA) eliminates the main deficiency of the standard affine arithmetic (AA), i.e. a gradual increase of the number of noise symbols, which makes AA inefficient in a long computation chain. To further reduce overestimation in RAA computation, a new algorithm for the Chebyshev minimum-error multiplication of reduced affine forms is proposed. The algorithm yields the minimum Chebyshev-type bounds and works in linear time, which is asymptotically optimal. We also propose a simplified \(\mathcal {O}(n\log n)\) version of the algorithm, which performs better for low dimensional problems. Illustrative examples show that the presented approach significantly improves solutions of many numerical problems, such as the problem of solving parametric interval linear systems or parametric linear programming, and also improves the efficiency of interval global optimisation.     

Grade Filtration of Linear Functional Systems

The grade (purity) filtration of a finitely generated left module M over an Auslander regular ring D is a built-in classification of the elements of M in terms of their grades (or their (co)dimensions if D is also a Cohen-Macaulay ring). In this paper, we show how grade filtration can be explicitly characterized by means of elementary methods of homological algebra. Our approach avoids using sophisticated methods such as bidualizing complexes, spectral sequences, associated cohomology, or Spencer cohomology used in the literature of algebraic analysis. Efficient implementations dedicated to the computation of grade filtration can then be easily developed in the standard computer algebra systems. Moreover, this characterization of grade filtration is shown to induce a new presentation of the left D-module M which is defined by a block-triangular matrix formed by equidimensional diagonal blocks. The linear functional system associated with the left D-module M can then be integrated in cascade by successively solving inhomogeneous linear functional systems defined by equidimensional homogeneous linear systems of increasing dimension. This equivalent linear system generally simplifies the computation of closed-form solutions of the original linear system. In particular, many classes of underdetermined/overdetermined linear systems of partial differential equations can be explicitly integrated by the Maple package PurityFiltration and the GAP package homalg, but not by the standard PDE solvers of computer algebra systems such as Maple.     

Parametric continuation of the solitary traveling pulse solution in the reaction-diffusion system using the Newton-Krylov method

The matrix-free Newton-Krylov method that uses the GMRES algorithm (an iterative algorithm for solving systems of linear algebraic equations) is used for the parametric continuation of the solitary traveling pulse solution in a three-component reaction-diffusion system. Using the results of integration on a short time interval, we replace the original system of nonlinear algebraic equations by another system that has more convenient (from the viewpoint of the spectral properties of the GMRES algorithm) Jacobi matrix. The proposed parametric continuation proved to be efficient for large-scale problems, and it made it possible to thoroughly examine the dependence of localized solutions on a parameter of the model.     

A kind of fuzzy linear programming problems based on interval-valued fuzzy sets

Abstract. The objective of this paper is to deal with a kind of fuzzy linear programming problem based on interval-valued fuzzy sets (IVFLP) through the medium of procedure that turns IVFLP into parametric linear programming via the mathematical programming. Some useful results for the benefit of solving IVFLP are expounded and proved,developed and discussed. Furthermore,that the proposed techniques in this paper allow the decision-maker to assign a different degree of importance can provide a useful way to efficiently help the decision-maker make their decisions.     

On preconditioning and solving an extended class of interval parametric linear systems

Numerical Algorithms - We deal with interval parametric systems of linear equations and the goal is to solve such systems, which basically comes down to finding an enclosure for a parametric...     

Web-Accessible Tools for Interval Linear Systems

Interval webComputing is a collection of dynamic interactive pages designed to make specialized interval computations and visualization widely accessible through web browsers. Discussed are the general conception and two typical components: visualization of solution sets to interval linear systems and solvers of parametric interval linear systems. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A software package for the simulation of second-harmonic generation in the three-dimensional case and visualization of the results in a windows environment

We describe a software package for visualizing the simulation results of second-harmonic generation in a medium with combined (quadratic-cubic) nonlinearity in the (z, r, t) coordinates. The package includes a wide range of graphical tools that create avi files, display intensity distributions of interacting waves, generate three-dimensional graphs with varying degree of detail, and plot various characteristics of the optical radiation. The package provides a user-friendly interface for analyzing a wide range of solutions and estimating the efficiency of energy transformation in the parameter plane that characterizes wave interaction. To this end the package represents the analytical solution of the problem in the long-pulse and plane-wave approximation allowing for quadratic and cubic nonlinearity of the medium. The analytical solution can be used also for testing simulation results. The software package is equipped with an interface for computing dimensionless parameters for the corresponding system of dimensionless Schrödinger equations from physical parameters specified in one of the systems of physical units. Options for DOS and Unix format conversions are provided, as the original computer program solving the nonlinear Schrödinger equations is designed for either Windows or Unix environments. The package has been applied to analyze various second-harmonic generation modes in a medium with combined (quadratic-cubic) nonlinearity.     

Iterative solver for systems of linear equations with a sparse stiffness matrix on clusters

In this paper, a package of programs for solving systems of linear equations with a sparse matrix for computers with distributed memory is proposed. The package is based on an iterative algorithm for solving the initial system of equations with a preconditioner constructed using an algebraic domain decomposition. Such an approach makes it possible to simultaneously multiply the preconditioner and the stiffness matrix by a vector on a cluster. Also, to improve the efficiency of computation, the functionalities PARDISO and Sparse BLAS of the Intel®MKL library are used on each process. In addition to processes parallelization, the package uses OpenMP parallelization on each of these processes, as well as Intel®MKL internal functional parallelization.     

Transformations of interval linear systems of equations and inequalities

Very recently, new results on transformation of interval linear systems and on generalizations of the Farkas lemma to interval systems appeared in the literature. They are by far not obvious since the standard transformations on linear systems are not easily adapted to interval system due to the dependency problem. The aim of this paper was to come up with new possible transformations and to extend the results to more general classes of AE interval systems and to linear parametric systems. We also show that the transformations can help in simplifying the proofs of some characterization theorems.     

An application of gomory cuts in number theory

Frobenius has stated the following problem. Suppose thata ₁, a₂, ?, a_n are given positive integers and g.c.d. (a ₁, ? , a_n) = 1. The problem is to determine the greatest positive integerg so that the equation $$\sum\limits_{i = 1}^n {a_i x_i = g} $$ has no nonnegative integer solution. Showing the interrelation of the original problem and discrete optimization we give lower bounds for this number using Gomory cuts which are tools for solving discrete programming problems. In the first section an important theorem is cited after some remarks. In Section 2 we state a parametric knapsack problem. The Frobenius problem is equivalent with finding the value of the parameter where the optimal objective function value is maximal. The basis of this reformulation is the above mentioned theorem. Gomory's cutting plane method is applied for the knapsack problem in Section 3. Only one cut is generated and we make one dual simplex step after cutting the linear programming optimum of the knapsack problem. Applying this result we gain lower bounds for the Frobenius problem in Section 4. In the last section we show that the bounds are sharp in the sense that there are examples with arbitrary many coefficients where the lower bounds and the exact solution of the Frobenius problem coincide.     

Interval Approach to Solving Parametric Identification Problems for Dynamical Systems

Differential Equations - We present an approach to solving parametric identification problems for dynamical systems. The approach is aimed at finding an interval estimate of the model parameters in...     

Comparative study on order-reduced methods for linear third-order ordinary differential equations

The linear third-order ordinary differential equation (ODE) can be transformed into a system of two second-order ODEs by introducing a variable replacement, which is different from the common order-reduced approach. We choose the functions p(x) and q(x) in the variable replacement to get different cases of the special order-reduced system for the linear third-order ODE. We analyze the numerical behavior and algebraic properties of the systems of linear equations resulting from the sinc discretizations of these special second-order ODE systems. Then the block-diagonal preconditioner is used to accelerate the convergence of the Krylov subspace iteration methods for solving the discretized system of linear equation. Numerical results show that these order-reduced methods are effective for solving the linear third-order ODEs.     

A MAPLE package of new ADM-Padé approximate solution for nonlinear problems

Based on the new definition of four classes of Adomian polynomials proposed by Rach in 2008, a MAPLE package of new Adomian-Padé approximate solution for solving nonlinear problems is presented. This package combines the merits of the Adomian decomposition method and the diagonal Padé technique, and may give more accurate solutions of nonlinear problems with strong nonlinearity. Besides, the package is user-friendly and efficient, one only needs to input the initial conditions, governing equation and four optional parameters, then our package will output the analytic approximate solution within a few seconds, where the equation is decomposed into three parts, they are the linear term R, nonlinear term NN and source function g, which are all in functional form. Meanwhile, several graphs generated from the above solutions are displayed and demonstrate a favorable comparison. In this paper, several different types of examples are given to illustrate the validity and promising flexibility of the package. This package provides us with a convenient and useful tool for dealing with nonlinear problems, as well as its electronic version is free to download via the journal website.     

A Monomial-by-Monomial Method for Computing Regular Solutions of Systems of Pseudo-Linear Equations

This paper deals with the local analysis of systems of pseudo-linear equations. We define regular solutions and use this as a unifying theoretical framework for discussing the structure and existence of regular solutions of various systems of linear functional equations. We then give a generic and flexible algorithm for the computation of a basis of regular solutions. We have implemented this algorithm in the computer algebra system Maple in order to provide novel functionality for solving systems of linear differential, difference and q-difference equations given in various input formats.     

A polynomial approach for generating a monoparametric family of chaotic attractors via switched linear systems

In this paper, we consider characteristic polynomials of n-dimensional systems that determine a segment of polynomials. One parameter is used to characterize this segment of polynomials in order to determine the maximal interval of dissipativity and unstability. Then we apply this result to the generation of a family of attractors based on a class of unstable dissipative systems (UDS) of type affine linear systems. This class of systems is comprised of switched linear systems yielding strange attractors. A family of these chaotic switched systems is determined by the maximal interval of perturbation of the matrix that governs the dynamics for still having scroll attractors.