Multipoint efficient iterative methods and the dynamics of Ostrowski's method

ABSTRACT

In this work, we introduce a modification into the technique, presented in A. Cordero, J.L. Hueso, E. Martínez, and J.R. Torregrosa [Increasing the convergence order of an iterative method for nonlinear systems, Appl. Math. Lett. 25 (2012), pp. 2369–2374], that increases by two units the convergence order of an iterative method. The main idea is to compose a given iterative method of order p with a modification of Newton's method that introduces just one evaluation of the function, obtaining a new method of order p+2, avoiding the need to compute more than one derivative, so we improve the efficiency index in the scalar case. This procedure can be repeated n times, with the same approximation to the derivative, obtaining new iterative methods of order p+2n. We perform different numerical tests that confirm the theoretical results. By applying this procedure to Newton's method one obtains the well known fourth order Ostrowski's method. We finally analyse its dynamical behaviour on second and third degree real polynomials.     

Basic ideas to support pressure ulcers treatment by means of image mining

A Pressure ulcer (PU) occurs in a significant amount of patients that must remain in bed without movements for long periods. To improve its treatment in order to increase patient life quality and to reduce medical healthcare is yet a challenge. It seems to be helpful to search for medical decision making information in both PU images features and in data concerning patient life so far. Once suitably stored such information sets data and image mining procedures are supposed to be able to allow inferences and finding of patient clusters. Is seems to be also possible computationally to generate a PU grade inference that will help medical experts to accomplish therapeutic procedures. Current research efforts with such purposes are here presented. The article is published in the original. Renato Guadagnin. Mechanical Engineer, Federal University of Rio de Janeiro (1969), Master of Systems Analysis, National Institute for Space Research (1972) and PhD, German University of Administrative Sciences, Speyer (1984). He is retired professor from University of Brasilia. He is currently professor at Catholic University of Brasilia. His scientific works concern: knowledge management, information technology management, artificial intelligence, image analysis and visualization. Rinaldo de S. Neves. Nursing and Obstetrics Bachelor University of Brasília (1992), Master of Health Sciences by University of Brasília (2002), PhD. Student in Health Sciences, University of Brasília (2008). Currently he is Manager of Professional Subjects of Brazilian Nursing Association in Brasilia. He has experience in Medical Chirurgical Nursing, mainly in nursing diagnosis and processes, systematizing of nursing cares, wounds treatment, and rehabilitation of patients with medullar lesion. Edvar F. Rocha Jr. Physiotherapy Bachelor, Catholic University of Brasilia, (2009). He has experience in Physical and Occupational Therapy, with emphasis on Physical and Occupational Therapy. Levy A. Santana. Physiotherapy Bachelor, Paulist State University Julio de Mesquita Filho (1991), Master in Health Sciences, University of Brasilia (1999). He has postgraduate studies in Mechanical Diagnosis and Therapy Method by Mackenzie Method. He is currently physiotherapist at Health State Secretary of Federal District and professor at Catholic University of Brasilia. He has experience in Physiotherapy, mainly on electrotherapy, orthopedics, pressure ulcers, biomechanical and postural stability. Edilson Ferneda. Computer Technology Bachelor, Technology Institute of Aeronautics (1979), Master in Computer Science, Federal University of Paraiba (1988), PhD in Informatics, Montpellier II University (1992). He is currently professor at Catholic University of Brasilia. He has experience in computer science, with emphasis on intelligent agents, artificial intelligence, intelligent systems tutors, computers in education, case-based reasoning and machine learning. Simonia F. Silva. Physiotherapy Bachelor, Catholic University of Brasilia, (2007). She presented the study Interobserver Agreement and Intraobserver Reproducibility in Evaluation of Pressure Ulcer Area in Pictures using Software Motic.     

Of Interest

Abstract

COMPUTER AUDITING, by Andrew D. Chambers. Commerce Clearing House, Inc., Chicago. 1981; 237 pages including index; $22.50. Reviewed by Robert V. Boos.     

Adaptive backstepping sliding mode control for feedforward uncertain systems

Output tracking backstepping sliding mode control for feedforward uncertain systems is considered in this article. Feedforward systems are not usually transformable to the parametric semi-strict feedback form, and they may include unmatched uncertainties consisting of disturbances and unmodelled dynamics terms. The backstepping method presented in this article, even without uncertainties differs from that of Ríos-Bolívar and Zinober [Ríos-Bolívar, M. and Zinober, A.S.I. (1999), ‘Dynamical Adaptive Sliding Mode Control of Observable Minimum Phase Uncertain Nonlinear Systems’, in Variable Structure Systems: Variable Structure Systems, Sliding Mode and Nonlinear Control, eds., K.D. Young and Ü. Özgüner. Ozguner, London, Springer-Verlag, pp. 211–236; Ríos-Bolívar, M., and Zinober, A.S.I. (1997a), ‘Dynamical Adaptive Backstepping Control Design via Symbolic Computation’, in Proceedings of the 3rd European Control Conference, Brussels]. In this article, the backstepping is not a dynamical method as in Ríos-Bolívar and Zinober (1997a Ríos-Bolívar, M and Zinober, ASI. 1997a. Dynamical Adaptive Sliding Mode Output Tracking Control of a Class of Nonlinear Systems. International Journal of Robust and Nonlinear Control, 7: 387–405.  [Google Scholar], 1999), since at each step, the control and map input remain intact, and the differentiations of the control are not used. Therefore, the method can be introduced as static backstepping. Two different controllers are designed based upon the backstepping approach with and without sliding mode. The dynamic and static backstepping methods are applied to a gravity-flow/pipeline system to compare two methods.     

A reconfigurable architecture for autonomous visual-navigation

Abstract. This paper describes the design of a reconfigurable architecture for implementing image processing algorithms. This architecture is a pipeline of small identical processing elements that contain a programmable logic device (FPGA) and double port memories. This processing system has been adapted to accelerate the computation of differential algorithms. The log-polar vision selectively reduces the amount of data to be processed and simplifies several vision algorithms, making possible their implementation using few hardware resources. The reconfigurable architecture design has been devoted to implementation, and has been employed in an autonomous platform, which has power consumption, size and weight restrictions. Two different vision algorithms have been implemented in the reconfigurable pipeline, for which some experimental results are shown. Received: 30 March 2001 / Accepted: 11 February 2002 RID="*" ID="*" This work has been supported by the Ministerio de Ciencia y Tecnología and FEDER under project TIC2001-3546 Correspondence to: J.A. Boluda     

Generation of robust root loci for linear systems with parametric uncertainties in an ellipsoid

Given a parametric polynomial family p(s; Q) := {ⁿ _k=0 a_k (q)s^k : q ] Q}, Q R ^m , the robust root locus of p(s; Q) is defined as the two-dimensional zero set _p,Q := {s ] C:p(s; q) = 0 for some q ] Q}. In this paper we are concerned with the problem of generating robust root loci for the parametric polynomial family p(s; E) whose polynomial coefficients depend polynomially on elements of the parameter vector q ] E which lies in an m-dimensional ellipsoid E. More precisely, we present a computational technique for testing the zero inclusion/exclusion of the value set p(z; E) for a fixed point z in C, and then apply an integer-labelled pivoting procedure to generate the boundary of each subregion of the robust root locus _p,E . The proposed zero inclusion/exclusion test algorithm is based on using some simple sufficient conditions for the zero inclusion and exclusion of the value set p(z,E) and subdividing the domain E iteratively. Furthermore, an interval method is incorporated in the algorithm to speed up the process of zero inclusion/exclusion test by reducing the number of zero inclusion test operations. To illustrate the effectiveness of the proposed algorithm for the generation of robust root locus, an example is provided.     

Local noncuppability in R/M

Given any [c],[a],[d]∈R/M such that [d]≤[a]≤[c], [a] is locally noncuppable between [c] and [d] if [d]<[a]≤[c]and [a] ∨ [b] < [c] for any [b]∈R/M such that [d]≤ [ b ] < [ c ]. It will be shown that given any nonzero [ c ] ∈ R/M, there are [ a ], [ d ] ∈R/M such that [d]<[a]≤[c] and[a] is locally noncuppable between [c] and[d].     

Compactness in <Emphasis Type="Italic">MV</Emphasis>-algebras and in their non-commutative generalizations

 In the paper we study MV-algebras and their non-commutative generalizations, GMV-algebras, in which every element is compact. Further, we characterize finite MV-algebras as archimedean GMV-algebras which are 0-meet compact. Dedicated to Prof. Ján Jakubík on the occasion of his 80th birthday Supported by the Council of Czech Government, J 14/98: 15100011.     

Local Approximability of Max-Min and Min-Max Linear Programs

In a max-min LP, the objective is to maximise ω subject to A x≤1, C x≥ω 1, and x≥0. In a min-max LP, the objective is to minimise ρ subject to A x≤ρ 1, C x≥1, and x≥0. The matrices A and C are nonnegative and sparse: each row a _i of A has at most Δ _I positive elements, and each row c _k of C has at most Δ _K positive elements.     

Feature space versus empirical kernel map and row kernel space in SVMs

In machine-learning technologies, the support vector machine (SV machine, SVM) is a brilliant invention with many merits, such as freedom from local minima, the widest possible margins separating different clusters, and a solid theoretical foundation. In this paper, we first explore the linear separability relationships between the high-dimensional feature space H and the empirical kernel map U as well as between H and the space of kernel outputs K. Second, we investigate the relations of the distances between separating hyperplanes and SVs in H and U, and derive an upper bound for the margin width in K. Third, as an application, we show experimentally that the separating hyperplane in H can be slightly adjusted through U. The experiments reveal that existing SVM training can linearly separate the data in H with considerable success. The results in this paper allow us to visualize the geometry of H by studying U and K.     

Least-squares problem for the quaternion matrix equation AXB+CYD=E over different constrained matrices

For any A=A ₁+A ₂ j∈Q ^n×n and η∈<texlscub>i, j, k</texlscub>, denote A ^{η H} =?η A ^H η. If A ^{η H} =A, A is called an $\eta$-Hermitian matrix. If A ^{η H} =?A, A is called an η-anti-Hermitian matrix. Denote η-Hermitian matrices and η-anti-Hermitian matrices by η HQ ^n×n and η AQ ^n×n , respectively.

By using the complex representation of quaternion matrices, the Moore–Penrose generalized inverse and the Kronecker product of matrices, we derive the expressions of the least-squares solution with the least norm for the quaternion matrix equation AXB+CYD=E over X∈η HQ ^n×n and Y∈η AQ ^n×n .     

Model Checking Abilities of Agents: A Closer Look

Alternating-time temporal logic (atl) is a logic for reasoning about open computational systems and multi-agent systems. It is well known that atl model checking is linear in the size of the model. We point out, however, that the size of an atl model is usually exponential in the number of agents. When the size of models is defined in terms of states and agents rather than transitions, it turns out that the problem is (1) Δ ₃ ^P -complete for concurrent game structures, and (2) Δ ₂ ^P -complete for alternating transition systems. Moreover, for “Positive atl” that allows for negation only on the level of propositions, model checking is (1) Σ ₂ ^P -complete for concurrent game structures, and (2) NP-complete for alternating transition systems. We show a nondeterministic polynomial reduction from checking arbitrary alternating transition systems to checking turn-based transition systems, We also discuss the determinism assumption in alternating transition systems, and show that it can be easily removed. In the second part of the paper, we study the model checking complexity for formulae of atl with imperfect information (atl _ir ). We show that the problem is Δ ₂ ^P -complete in the number of transitions and the length of the formula (thereby closing a gap in previous work of Schobbens in Electron. Notes Theor. Comput. Sci. 85(2), 2004). Then, we take a closer look and use the same fine structure complexity measure as we did for atl with perfect information. We get the surprising result that checking formulae of atl _ir is also Δ ₃ ^P -complete in the general case, and Σ ₂ ^P -complete for “Positive atl _ir ”. Thus, model checking agents’ abilities for both perfect and imperfect information systems belongs to the same complexity class when a finer-grained analysis is used.     

正交约束多头自注意力的场景文本识别

目的 场景文本识别（scene text recognition，STR）是计算机视觉中的一个热门研究领域。最近，基于多头自注意力机制的视觉Transformer （vision Transformer，ViT）模型被提出用于STR，以实现精度、速度和计算负载的平衡。然而，没有机制可以保证不同的自注意力头确实捕捉到多样性的特征，这将导致使用多头自注意力机制的ViT模型在多样性极强的场景文本识别任务中表现不佳。针对这个问题，提出了一种新颖的正交约束来显式增强多个自注意力头之间的多样性，提高多头自注意力对不同子空间信息的捕获能力，在保证速度和计算效率的同时进一步提高网络的精度。方法 首先提出了针对不同自注意力头上Q （query）、K （key）和V （value）特征的正交约束，这可以使不同的自注意力头能够关注到不同的查询子空间、键子空间、值子空间的特征，关注不同子空间的特征可以显式地使不同的自注意力头捕捉到更具差异的特征。还提出了针对不同自注意力头上Q 、K 和V 特征线性变换权重的正交约束，这将为Q、K和V特征的学习提供正交权重空间的解决方案，并在网络训练中带来隐式正则化的效果。结果 实验在7个数据集上与基准方法进行比较，在规则数据集Street View Text （SVT）上精度提高了0.5%；在不规则数据集CUTE80 （CT）上精度提高了1.1%；在7个公共数据集上的整体精度提升了0.5%。结论 提出的即插即用的正交约束能够提高多头自注意力机制在STR任务中的特征捕获能力，使ViT模型在STR任务上的识别精度得到提高。本文代码已公开： https：//github.com/lexiaoyuan/XViTSTR。     

On solving a special class of weakly nonlinear finite-difference systems

In this paper, we consider the Newton-iterative method for solving weakly nonlinear finite-difference systems of the form F ( u )=A u + G ( u )=0, where the jacobian matrix G′( u ) satisfies an affine invariant Lipschitz condition. We also consider a modification of the method for which we can improve the likelihood of convergence from initial approximations that may be outside the attraction ball of the Newton-iterative method. We analyse the convergence of this damped method in the framework of the line search strategy. Numerical experiments on a diffusion–convection problem show the effectiveness of the method.     

A geometrical solution to time series searching invariant to shifting and scaling

The technique of searching for similar patterns among time series data is very useful in many applications. The problem becomes difficult when shifting and scaling are considered. We find that we can treat the problem geometrically and the major contribution of this paper is that a uniform geometrical model that can analyze the existing related methods is proposed. Based on the analysis, we conclude that the angle between two vectors after the Shift-Eliminated Transformation is a more intrinsical similarity measure invariant to shifting and scaling. We then enhance the original conical index to adapt to the geometrical properties of the problem and compare its performance with that of sequential search and R^*-tree. Experimental results show that the enhanced conical index achieves larger improvement on R^*-tree and sequential search in high dimension. It can also keep a steady performance as the selectivity increases. Part of the result related to the geometrical model has been published in the Proceedings of the 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp 237–248. Mi Zhou was born in China. He received his BS and MS degrees in computer science from the Northeastern University, China, in 1999 and 2002, respectively. He is currently pursuing the Ph D degree in the Computer Science and Engineering Department, The Chinese University of Hong Kong. His research interests include indexing of time series data, high-dimensional index, and sensor network. Man-Hon Wong received his BSc and MPhil degrees from The Chinese University of Hong Kong in 1987 and 1989 respectively. He then went to University of California at Santa Barbara where he got the PhD degree in 1993. Dr. Wong joined The Chinese University of Hong Kong in August 1993 as an assistant professor. He was promoted to associate professor in 1998. His research interests include transaction management, mobile databases, data replication, distributed systems, and computer and network security. Kam-Wing Chu was born in Hong Kong. He received his BS and MPhil degrees in computer science and engineering from The Chinese University of Hong Kong. When he was in Hong Kong, his research interests included database indexing of high dimensional data, and data mining. He later went to United States and received his MS degree in computer science from University of Maryland at College Park. While he was in Maryland, he focused on high performance implementation and algorithm design of advanced database systems. He is currently a senior software engineer in Server Performance group at Actuate Corporation. His expertise is in enterprise software development and software performance optimization.     

Some consequences on the planar three-index transportation problem

In this study, some algebraic characterizations of the coefficient matrix A of the planar three-index transportation problem are derived and the equivalent formulation of this problem is obtained using the Kronecker product. It is shown that eigenvectors of the matrix G ⁺ G are characterized in terms of eigenvectors of the matrix A ⁺ A , where G ⁺ is the Moore–Penrose inverse of the coefficient matrix G of the equivalent problem.     

A generalized Schur-type algorithm for the joint factorization of a structured matrix and its inverse

A Schur-type algorithm is presented for the simultaneous triangular factorization of a given (non-degenerate) structured matrix and its inverse. The algorithm takes the displacement generator of a Hermitian, strongly regular matrixR as an input, and computes the displacement generator of the inverse matrixR ⁻¹ as an output. From these generators we can directly deduce theLD ⁻¹ L ^* (lower-diagonal-upper) decomposition ofR, and theUD ⁻¹ U ^* (upper-diagonallower) decomposition ofR ⁻¹. The computational complexity of the algorithm isO(rn ²) operations, wheren andr denote the size and the displacement rank ofR, respectively. Moreover, this method is especially suited for parallel (systolic array) implementations: usingn processors the algorithm can be carried out inO(n) steps.     

Optimum Control of a Certain Class of Servomechanism†

Linear control systems governed by the vector matrix differential equation x = A x + B u have been considered. It has been shown how to find the optimum control u so that the system, starting from an initial position x(0), is steered to a state specifying the first p coordinates of the system in time t _o fixed in advance, the values attained by the (n—p) coordinates being immaterial, where n is the dimension of the system. The optimization considered here is with regard to the norm of u supposed to belong to L _m E _r space.     

The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems

In this paper we separate many-one reducibility from truth-table reducibility for distributional problems in DistNP under the hypothesis that P ≠ NP . As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We show that 3SAT with a version of the standard distribution is truth-table reducible but not many-one reducible to 3SAT with a less redundant distribution unless P = NP . We extend this separation result and define a distributional complexity class C with the following properties: (1) C is a subclass of DistNP, this relation is proper unless P = NP. (2) C contains DistP, but it is not contained in AveP unless DistNP \subseteq AveZPP. (3) C has a ≤ ^p _m -complete set. (4) C has a ≤ ^p _tt -complete set that is not ≤ ^p _m -complete unless P = NP. This shows that under the assumption that P ≠ NP, the two completeness notions differ on some nontrivial subclass of DistNP.