Formulation of linear problems and solution by a universal machine

Using the predicate language for ordered fields a class of problems referred to aslinear problems is defined. This class contains, for example, all systems of linear equations and inequalities, all linear programming problems, all integer programming problems with bounded variables, all linear complementarity problems, the testing of whether sets that are defined by linear inequalities are semilattices, all satisfiability problems in sentenial logic, the rank-computation of matrices, the computation of row-reduced echelon forms of matrices, and all quadratic programming problems with bounded variables. A single, one, algorithm, to which we refer as theUniversal Linear Machine, is described. It solves any instance of any linear problem. The Universal Linear Machine runs in two phases. Given a linear problem, in the first phase a Compiler running on a Turing Machine generates alinear algorithm for the problem. Then, given an instance of the linear problem, in the second phase the linear algorithm solves the particular instance of the linear problem. The linear algorithm is finite, deterministic, loopless and executes only the five ordered field operations — additions, multiplications, subtractions, divisions and comparisons. Conversely, we show that for each linear algorithm there is a linear problem which the linear algorithm solves uniquely. Finally, it is shown that with a linear algorithm for a linear problem, one can solve certain parametric instances of the linear problem.Research was supported in part by the National Science Foundation Grant DMS 92-07409, by the Department of Energy Grant DE-FG03-87-ER-25028, by the United States—Israel Binational Science Foundation Grant 90-00434 and by ONR Grant N00014-92-J1142.Corresponding author.     

并行分批排序综述

并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。     

A double-stage piecewise recursive filter for real-time applications

This paper examines the basic problem of estimating the state of a system described by a set of dynamical equations. The state estimation is performed by means of optimal filtering techniques in which the state observation is given by a set of nonlinear equations.The basic issue encountered in most engineering problems is the availability of more observable information than the processor can effectively process in real-time, while performing full optimal filtering on all available observable data. To alleviate this deficiency, an algorithm is developed in which the rate of information processing is kept at a high value, while the system statistics are evaluated at a much slower rate.The method utilizes a combination of fast and slow filtering loops, in which the observable data are processed at a high rate during the fast loop, while the system error covariance, gain computations, and all other system statistics are processed at a lower rate in the slow loop. Methods are provided to resolve any incompatibility in the system statistics resulting from this fast-loop/slow-loop processing combination.Applications describing problems pertaining to aircraft navigation are presented. Specifically, applications to aircraft navigation through a satellite network are studied. Appropriate simulation results from the above studies are shown.This work was performed under contract with the Department of the Air Force, Space and Missile Organization (SAMSO), Los Angeles, California, Contract No. F04-701-75-C-0180.The authors are indebted to Dr. C. Johnson, GPS System Engineer, Mr. G. Consolver, GPS Software Manager, and Mr. W. Riley, Communications/Navigation Department, Texas Instruments for their continuous encouragement in the course of this work. Also, they are indebted to Major M. Birnbaum, SAMSO, for his constructive criticism on the conceptual design of this work, and to Mr. A. Bierman, Aerospace Corporation, for kindly providing simulation data of aircraft trajectories. Finally, the authors would like to express their gratitude to Dr. N. Carlson, Intermetrics, for valuable consultation during the progress of this work.Portions of this paper were presented by the senior author at the GSP Conference, Plan 76, IEEE Position, Location, and Navigation Symposium, San Diego, California, 1976.     

基于模糊FNN-ELECTRE法的国有商业银行竞争力评价

随着金融业全方位开放,国有商业银行已成为国家经济命脉的核心,其竞争力强弱关系着国家经济的繁荣与衰退。本文基于模糊FNN-ELECTRE方法建立国有商业银行竞争力评价模型,以因素神经网络理论(FNN)与ELECTRE融合方法为基础,以现有商业银行竞争力评价指标为着眼,把国有商业银行竞争力的评价体系从现实竞争力和潜在竞争力两个因素抽取为一级指标,以规模、质量、业务结构、效率、成长性五个因素设为二级指标。从实证的角度对银行A、银行B、银行C、银行D、银行E五大国有银行进行分析验证,对其属性值进行和谐性与非和谐性检验得出,银行B竞争能力最强,银行E竞争能力最弱,五大国有银行均有改进空间。     

On the weakening of the convergence of Newton’s method using recurrent functions

We use Newton’s method to approximate a locally unique solution of an equation in a Banach space setting. We introduce recurrent functions to provide a weaker semilocal convergence analysis for Newton’s method than before [J. Appell, E. De Pascale, J.V. Lysenko, P.P. Zabrejko, New results on Newton–Kantorovich approximations with applications to nonlinear integral equations, Numer. Funct. Anal. Optim. 18 (1997) 1–17; I.K. Argyros, The theory and application of abstract polynomial equations, in: Mathematics Series, St. Lucie/CRC/Lewis Publ., Boca Raton, Florida, USA, 1998; I.K. Argyros, Concerning the “terra incognita” between convergence regions of two Newton methods, Nonlinear Anal. 62 (2005) 179–194; I.K. Argyros, Convergence and Applications of Newton-Type Iterations, Springer-Verlag Publ., New York, 2008; S. Chandrasekhar, Radiative Transfer, Dover Publ., New York, 1960; F. Cianciaruso, E. De Pascale, Newton–Kantorovich approximations when the derivative is Hölderian: Old and new results, Numer. Funct. Anal. Optim. 24 (2003) 713–723; N.T. Demidovich, P.P. Zabrejko, Ju.V. Lysenko, Some remarks on the Newton–Kantorovich method for nonlinear equations with Hölder continuous linearizations, Izv. Akad. Nauk Belorus 3 (1993) 22–26. (in Russian); E. De Pascale, P.P. Zabrejko, Convergence of the Newton–Kantorovich method under Vertgeim conditions: A new improvement, Z. Anal. Anwendvugen 17 (1998) 271–280; L.V. Kantorovich, G.P. Akilov, Functional Analysis, Pergamon Press, Oxford, 1982; J.V. Lysenko, Conditions for the convergence of the Newton–Kantorovich method for nonlinear equations with Hölder linearizations, Dokl. Akad. Nauk BSSR 38 (1994) 20–24. (in Russian); B.A. Vertgeim, On conditions for the applicability of Newton’s method, (Russian), Dokl. Akad. Nauk., SSSR 110 (1956) 719–722; B.A. Vertgeim, On some methods for the approximate solution of nonlinear functional equations in Banach spaces, Uspekhi Mat. Nauk 12 (1957) 166–169. (in Russian); English transl.:; Amer. Math. Soc. Transl. 16 (1960) 378–382] provided that the Fréchet-derivative of the operator involved is p$p$-Hölder continuous (p∈(0,1]$p\in (0,1]$).     

Holomorphic manifolds on locally convex spaces

Based on locally compact perturbations of the identity map similar to the Fredholm structures on real Banach manifolds, complex manifolds with inverse mapping theorem as part of the defintion are proposed. Standard topics including holomorphic maps, morphisms, derivatives, tangent bundles, product manifolds and submanifolds are presented. Although this framework is elementary, it lays the necessary foundation for all subsequent developments.     

泛系分析:数学·方法论·相对论·辩证思维

基于对广义系统、泛导、泛对称、泛箱原理、泛系相对性提出了新的分析模式与新的相对数学化的简化强化的定义,发展了泛系方法论与泛系相对论的框架与理法,具体内容涉及:相对普适的数学化的泛系,200类对偶,对偶转化,泛对称转化,泛系辩证,八畴方法,泛系数学方法,广义量化,逼近转化原则,泛等价定理,供求分析,思维实验,广义灰色系统,等等.     

Personae at play. ‘Men of Mathematics’ in commentary

Mathematical writers, above all, Euclid, tend to present their theorems as decontextualized, abstract propositions, which has become the standard modus of textual presentation in theoretical mathematics. Mathematical commentators, however, provide their readers with personal names and historical facts in order to elucidate problems, provide contexts of discovery, or construct doxographies, among other things. Modern readers have used such information for the construction of histories of science. When we look at these passages, however, we see that personal names and information about mathematicians of the past can serve quite a range of different objectives, such as the strategic self-positioning of the commentator vis-à-vis the past or present of mathematics, the education of the reader, mathematical or moral, the construction of the history of the field, etc. Not only does the commentator present a persona of himself to the reader, he can also turn colleagues and predecessors into personae. This paper attempts to elucidate the practice, by offering four examples of such plays of and with personae, in Pappus, Eutocius, al-Nayrīzī, and Proclus.     

提高维吾尔文搜索质量的一些关键技术研究

维吾尔语和土耳其语、乌兹别克语、哈萨克语等同属于阿尔泰语系突厥语分支,是一种粘着型语言,具有丰富的构词合构形附加成分.主要分布于中国新疆维吾尔自治区,以及中西亚地区的维吾尔族使用.目前使用基于阿拉伯文字母的维吾尔文.当前用google,bing等搜索引擎搜索维吾尔文时搜索结果不包括该词语的构词合构形附加成分等其它形式.严重影响了搜索结果的准确性.通过词干提取和词缀附加生成词语组合的方法以解决提高维吾尔文搜索质量的问题.此问题解决,将在大幅度提高维吾尔文搜索的准确性,并针对提高其它突厥语族语言(土耳其语、乌兹别克语、哈萨克语等)的搜索质量、数据挖掘、数据分析、数据安全、自然语言理解等研究领域有一定的参考价值.     

Representation of the solution to a model problem in semiconductor physics

We study a mixed type problem for the Poisson equation arising in the modeling of charge transport in semiconductor devices [V. Romano, 2D simulation of a silicon MESFET with a non-parabolic hydrodynamical model based on the maximum entropy principle, J. Comput. Phys. 176 (2002) 70-92; A.M. Blokhin, R.S. Bushmanov, A.S. Rudometova, V. Romano, Linear asymptotic stability of the equilibrium state for the 2D MEP hydrodynamical model of charge transport in semiconductors, Nonlinear Anal. 65 (2006) 1018-1038]. Unlike well-studied elliptic boundary-value problems in domains with smooth boundaries (see, for example, [O.A. Ladyzhenskaya, N.N. Uralceva, Linear and Quasilinear Elliptic Equations, Nauka, Moscow, 1973; D. Gilbarg, N.S. Trudinger, Elliptic Partial Differential Equations of Second Order, Springer-Verlag, Berlin, 1983]), our problem has two significant features: firstly, the boundary is not a smooth curve and, secondly, the type of boundary conditions is mixed (the Dirichlet condition is satisfied on the one part of the boundary whereas the Neumann condition on the other part). The well-posedness of the problem in Hölder and Sobolev spaces is proved. The representation of the solution to the problem is obtained in an explicit form.     

超大规模集成电路布局的优化模型与算法

布局确定集成电路单元在芯片中的具体位置,在单元互不重叠的基础上优化一些性能指标。该问题是NP困难的组合优化问题,是超大规模集成电路物理设计的核心问题之一,对集成电路的性能指标,如线网可布通性、时延、功耗、电路可靠性等有重大影响。在现代的集成电路设计中,布局问题通常包含数百万个集成电路单元,以及大小相异的异质性模块,和各种复杂的布局约束。目前的超大规模集成电路布局算法通常分解为总体布局、布局合法化和详细布局三个步骤。根据近年来集成电路布局算法的研究进展,综述并分析集成电路的总体布局、布局合法化和详细布局的相关优化模型和算法,并展望进一步的研究方向。     

Morphic环和G-morphic环的一些结果

讨论了morphic环,G-morphic环,PP环,GPP环,Bear环与正则环之间的关系.还证明了在约化环中,强正则环,正则环,π-正则环,G-π-正则环的等价性.     

Transverse compression of PPTA fibers

Results of single transverse compression testing of PPTA and PIPD fibers, using a novel test device, are presented and discussed. In the tests, short lengths of single fibers are compressed between two parallel, stiff platens. The fiber elastic deformation is analyzed as a Hertzian contact problem. The inelastic deformation is analyzed by elastic-plastic FE simulation and by laser-scanning confocal microscopy of the compressed fibers ex post facto. The results obtained are compared to those in the literature and to the theoretical predictions of PPTA fiber transverse elasticity based on PPTA crystal elasticity.Presented at the 11th International Conference on Mechanics of Composite Materials (Riga, June 11–15, 2000).3TEX, Inc. 109, MacKenan Drive, Cary, North Carolina 27511, USA. Published in Mekhanika Kompozitnykh Materialov, Vol. 36, No. 4, pp. 533–544, March–April, 2000.     

某一类色唯一的K_4-同胚图

令K_4(i,j,k,l,m,n)表示两两三度点间的路长分别为i,j,k,l,m,n的K_4-同胚图.对6条路的长均大于1且有4条路的长相等其余两条路互不相等的K_4-同胚图的着色进行了研究,得到了一类色唯一的K_4-同胚图.     

Remainders in compactifications and generalized metrizability properties

When does a Tychonoff space X have a Hausdorff compactification with the remainder belonging to a given class of spaces? A classical theorem of Henriksen and Isbell and certain theorems, involving a new completeness type property introduced below, are applied to obtain new results on remainders of topological spaces and groups. In particular, some strong necessary conditions for a topological group to have a metrizable remainder, or a paracompact p-remainder, are established (the group itself turns out to be a paracompact p-space (Theorem 4.8)). It follows that if a non-locally compact topological group G is metrizable at infinity, then G is a Lindelöf p-space, and the Souslin number of G is countable (Corollary 4.10). This solves Problem 10.28 from [M. Hušek, J. van Mill (Eds.), Recent Progress in General Topology, vol. 2, North-Holland, 2002, pp. 1–57].     

具有Heyting结构的Ockham代数

引入一个具有Heyting结构Ockham代数,简称HO-代数．所谓HO-代数,是指具有（2,2,2,1,0,0）类型的代数（L;∧,∨,→,f,0,1）．其中（L;f）是Ockham代数,（L;→）是Heyting代数,且运算f和→由恒等式f（x→y）=f^2（x）∧f（y）与f（x）→y=f^2（x）∨y所连结．主要讨论了HO-代数的同余关系的性质．并刻画了其次直不可约代数的某些性质．