Algebraic complexities and algebraic curves over finite fields

Algebraic schemes of computation of bilinear forms over various rings of scalars are examined. The problem of minimal complexity of these schemes is considered for computation of polynomial multiplication and multiplication in commutative algebras, and finite extensions of fields. While for infinite fields minimal complexities are known (Winograd, Fiduccia, Strassen), for finite fields precise minimal complexities are not yet determined. We prove lower and upper bounds on minimal complexities. Both are linear in the number of inputs. These results are obtained using the relationship with linear coding theory and the theory of algebraic curves over finite fields.     

Chebyshev model arithmetic for factorable functions

This article presents an arithmetic for the computation of Chebyshev models for factorable functions and an analysis of their convergence properties. Similar to Taylor models, Chebyshev models consist of a pair of a multivariate polynomial approximating the factorable function and an interval remainder term bounding the actual gap with this polynomial approximant. Propagation rules and local convergence bounds are established for the addition, multiplication and composition operations with Chebyshev models. The global convergence of this arithmetic as the polynomial expansion order increases is also discussed. A generic implementation of Chebyshev model arithmetic is available in the library MC++. It is shown through several numerical case studies that Chebyshev models provide tighter bounds than their Taylor model counterparts, but this comes at the price of extra computational burden.     

Operations over scalar polynomials and their computer realization

In this paper, algorithms which realize some operations over scalar polynomials in one and two variables and their computer realization are suggested. The following operations are considered: 1) the computation of the GCD for given scalar polynomials and the decomposition of each polynomial into a product of two factors: the first factor is the GCD, and the second factors form a sequence of relatively prime polynomials; 2) the division of polynomials by their common divisor; 3) the decomposition of polynomials in two variables into irreducible factors; 4) the computation of the LCM for given scalar polynomials. Bibliography: 5 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 219, 1994, pp. 158–175. This work was supported by the Russian Foundation of Fundamental Research (grant 94-01-00919). Translated by V. N. Kublanovskaya.     

Relaxed fuzzy observer‐based output feedback control synthesis of discrete‐time nonlinear control systems

This work develops the development of observer‐based output feedback control design of discrete‐time nonlinear systems in the form of Takagi–Sugeno fuzzy model. Lately, previous results have been improved in virtue of a two‐step method. From a technical point of view, it is not flawless and related problems have not been completely resolved. In this study, more advanced two‐steps approach is further developed while the relative sizes among different normalized fuzzy weighting functions are utilized by introducing some additional matrix variables. As a result of the above work, those main defects of the existing method can be redressed and a desired solution in aspect of not only reducing the conservatism but also alleviating the computation complexity is provided for some special cases. Moreover, the effectiveness of the proposed result is shown at length by means of an illustrative example. © 2016 Wiley Periodicals, Inc. Complexity 21: 593–601, 2016     

Parallel information-based complexity

We develop the theory of information-based complexity from a parallel point of view. For a model of computation with p processors, each being capable of arithmetic operations and decisions, we analyze the complexity of function approximation, numerical integration, and solution of Fredholm integral equations. We obtain tight bounds on the complexity, considered as a function of three variables simultaneously: the number of processors, the required precision, and (in the case of approximation and integral equations) the number of points, in which the approximate solution is to be determined.     

Some Reliability Models of Production Lines,with Special Reference to Computer Operation and Scheduling

A situation is considered where a machine or a production line, for example an electronic computer or a data-processing system, has alternate "good" and "bad" periods of operation. Two types of model are described which can be used to tackle this kind of situation and these form an approach to the practical problem of scheduling work through such a system. The two aspects considered are the probability of a preassigned schedule of operation being completed within some critical time, and the optimum assignment of the length of the scheduled operations.     

Students’ whole number multiplicative concepts: A critical constructive resource for fraction composition schemes

This article reports on the activity of two pairs of sixth grade students who participated in an 8-month teaching experiment that investigated the students’ construction of fraction composition schemes. A fraction composition scheme consists of the operations and concepts used to determine, for example, the size of 1/3 of 1/5 of a whole in relation to the whole. Students’ whole number multiplicative concepts were found to be critical constructive resources for students’ fraction composition schemes. Specifically, the interiorization of two levels of units, a particular multiplicative concept, was found to be necessary for the construction of a unit fraction composition scheme, while the interiorization of three levels of units was necessary for the construction of a general fraction composition scheme. These findings contribute to previous research on students’ construction of fraction multiplication that has emphasized partitioning and conceptualizing quantitative units. Implications of the findings for teaching are considered.     

On NP-Completeness for Linear Machines

We consider linear and scalar versions of the Blum–Shub–Smale model of computation over the reals. The permitted computing operations of linear machines are addition and multiplication by constants. The scalar machines can only multiply by constants. The size of an input is its dimension, and the cost of any instruction is one. For each of these structures we consider DNP and NP, the corresponding complexity classes with respect to digital nondeterminism and standard real nondeterminism, respectively. We give DNP- and NP-complete problems for linear and real scalar machines. On the other hand, we show that the NP-class restricted to scalar machines over the integers with equality-tests does not own a complete problem.     

Formal Laurent series in several variables

We explain the construction of fields of formal infinite series in several variables, generalizing the classical notion of formal Laurent series in one variable. Our discussion addresses the field operations for these series (addition, multiplication, and division), the composition, and includes an implicit function theorem.     

A flow-mode,self-steering,cellular multiplier-summation processor

Flow-mode or stream-processing digital systems have been proposed in which code, control and data are constantly moving so that multiple instructions are processed concurrently. We show the design of a flow-mode cellular array processor which can perform a number of two's complement fixed-point arithmetic operations. These operations are: three operand addition and/or subtraction, two operand multiplication and vector inner-product. Operand sizes are: 2N bit for addition and subtraction operands, andN bit for multiplication operands. Results are 2N bit. The network can simultaneously operate on 4N+2 datasets with any mix of the above operations being handled. The processor is based on the use of asynchronous cellular arrays. Given a continued flow of input datasets, the effective computation time is worst-case propagation time within one cell. A typical cell contains a 1-bit position 3-input full adder with associated input data storage. Thus the effective computation time is independent of the operand bit length.     

Subtraction-Free Complexity,Cluster Transformations,and Spanning Trees

Subtraction-free computational complexity is the version of arithmetic circuit complexity that allows only three operations: addition, multiplication, and division. We use cluster transformations to design efficient subtraction-free algorithms for computing Schur functions and their skew, double, and supersymmetric analogues, thereby generalizing earlier results by P. Koev. We develop such algorithms for computing generating functions of spanning trees, both directed and undirected. A comparison to the lower bound due to M. Jerrum and M. Snir shows that in subtraction-free computations, “division can be exponentially powerful.” Finally, we give a simple example where the gap between ordinary and subtraction-free complexity is exponential.     

Short-Time Linear Response with Reduced-Rank Tangent Map

The recently developed short-time linear response algorithm, which predicts the response of a nonlinear chaotic forced-dissipative system to small external perturbation, yields high precision of the response prediction. However, the computation of the short-time linear response formula with the full rank tangent map can be expensive. Here, a numerical method to potentially overcome the increasing numerical complexity for large scale models with many variables by using the reduced-rank tangent map in the computation is proposed. The conditions for which the short-time linear response approximation with the reduced-rank tangent map is valid are established, and two practical situations are examined, where the response to small external perturbations is predicted for nonlinear chaotic forced-dissipative systems with different dynamical properties.     

Relation between two measures of the computation complexity for systems of monomials

For a class of matrices defining exponents of variables in a system of monomials, a nontrivial lower bound of complexity is found (where the complexity is defined as the minimum number of multiplications required to compute the system starting from variables). An example of a sequence of matrices (systems of monomials, respectively) is also given so that the usage of inverse values of variables (in addition to the variables themselves) makes the complexity asymptotically two times less.     

The period on a family of non-linear oscillations and periodic motions of a perturbed system at a critical point of the family

Single-frequency oscillations of a reversible mechanical system are considered. It is shown that the oscillation period of a non-linear system usually only depends on a single parameter and it is established that, at a critical point of the family, at which the derivative of the period with respect to the parameter vanishes, due to the action of perturbations two families of symmetrical resonance periodic motions are produced. The oscillations of a satellite in an elliptic orbit, due to the action of gravitational and aerodynamic moments, are considered as an example. The operations in a circular orbit are investigated in detail initially, and then in an elliptical orbit of small eccentricity.     

一类平面多项式微分系统赤道环量的代数递推公式

本文研究一类形式相当一般的平面多项式系统赤道环量(Gauss球面的无穷远点奇点量)的计算,建立了系统赤道环量计算的简明的线性代数递推公式.应用递推公式计算赤道环量,只需用系统系数做四则运算,避免了通常计算赤道环量需要的复杂的积分运算和解方程,极易用计算机代数系统作符号推导并且不含舍入误差.     

A Refined Model of Computation for Continuous Problems

The real-number model of computation is used in computational geometry, in the approach suggested by Blum, Shub, and Smale and in information based complexity. In this paper we propose a refinement of this model, the TTE-model of computation. In contrast to the real-number model, which is unrealistic or at least too optimistic, the TTE-model is very realistic; i.e., for TTE-algorithms there are digital computers, which behave exactly the same way as predicted by the theoretical model. We start with a detailed discussion of some objections to the real-number model. We introduce the refined model by adding the condition “every partial input or output information of an algorithm is finite” to the assumptions of the IBC-model of computation. First, we explain computability and computational complexity in TTE for the simple case of real functions. Then we apply the refined model to two typical IBC-problems, integration and zero-finding on the spaceC[0; 1] of continuous real functions. We study computability and computational complexity and compare TTE-results with IBC-results. Finally, we briefly discuss the computation of discontinuous problems. This paper does not present new technical results but should be considered as a fresh impetus to reflect on models of computation for numerical analysis and as an invitation to try out the TTE-model of computation in information based complexity.     

Generalized fuzzy set systems and particularization

It is suggested that there exists many fuzzy set systems, each with its specific pointwise operations for union and intersection. A general law of compound possibilities is valid for all these systems, as well as a general law for representing marginal possibility distributions as unions of fuzzy sets. Max-min fuzzy sets are a special case of a fuzzy set system which uses the pointwise operations of max and min for union and intersection respectively. Probabilistic fuzzy sets are another special case which uses the operations of addition and multiplication. Probably there exists an infinite number of fuzzy set operations and systems. It is shown why the law of idempotency for intersection is not required for such systems. An essential difference between the meaning of the operations of union and intersection in traditional measure theory as compared with their meaning in the theory of possibility is pointed out. The operation of particularization is used to illustrate that the two distinct classical theories of nonfuzzy relations and of probability are merely two aspects of a more generalized theory of fuzzy sets. It is shown that we must distinguish between particularization of conditional fuzzy sets and of joint fuzzy sets. The concept of restriction of nonfuzzy relations is a special case of particularization of both conditional and joint fuzzy sets. The computation of joint probabilities from conditional and marginal ones is a special case of particularization of conditional probabilistic fuzzy sets. The difference between linguistic modifiers of type 1 and particulating modifiers is pointed out, as well as a general difference between nouns and adjectives.     

最优消除顺序

本文从一个离散最优化问题的算法复杂性出发,提出了图论中一个新的而有趣的问题:图的节点最优消除顺序.这一问题不仅有实用价值,而且有理论意义.本文只得到该问题的部分结果,并提出了若干待解决的问题,供有兴趣的读者进行研究.     

Topological Complexity of Zero-Finding

The topological complexity of zero-finding is studied using a BSS machine over the reals with an information node. The topological complexity depends on the class of functions, the class of arithmetic operations, and on the error criterion. For the root error criterion the following results are established. If only Hölder operations are permitted as arithmetic operations then the topological complexity is roughly −log₂ε and bisection is optimal. This holds even for the small class of linear functions. On the other hand, for the class of all increasing functions, if we allow the sign function or division, together with log and exp, then the topological complexity drops to zero. For the residual error criterion, results can be totally different than for the root error criterion. For example, the topological complexity can be zero for the residual error criterion, and roughly −log₂ε for the root error criterion.     

模糊数四则运算的交点-间断点法

对模糊数的四则运算提出了一种交点-间断点法:将模糊数的加法、减法和除法运算,化为求两个函数在某区间上其交点处的值;当交点不存在且两函数在该区间上的间断点为有限个时,将其运算化为求一函数在这些间断点处及区间的两端点处的最大值;将模糊数的乘法运算,化为用交点法或间断点法分别在两个区间上求出相应的值,然后取它们中最大者。