The Bisymplectomorphism Group of a Bounded Symmetric Domain

We determine the group of diffeomorphisms of a bounded symmetric domain, which preserve simultaneously the hyperbolic and the at symplectic form. *Research partially supported by GNSAGA (INdAM) and MIUR of Italy; MIUR Project “Geometric Properties of Real and Complex Manifolds” (PRIN05). **Research partially supported by GNSAGA (INdAM) and MIUR of Italy; MIUR Project “Geometric Properties of Real and Complex Manifolds” (PRIN05). ***Part of this work was done in July 2007 during a visit of G. Roos at Politecnico di Torino; visit supported by GNSAGA (INdAM) and MIUR of Italy; MIUR Project “Geometric Properties of Real and Complex Manifolds: (PRIN05).     

Inner solvers for interior point methods for large scale nonlinear programming

This paper deals with the solution of nonlinear programming problems arising from elliptic control problems by an interior point scheme. At each step of the scheme, we have to solve a large scale symmetric and indefinite system; inner iterative solvers, with an adaptive stopping rule, can be used in order to avoid unnecessary inner iterations, especially when the current outer iterate is far from the solution. In this work, we analyse the method of multipliers and the preconditioned conjugate gradient method as inner solvers for interior point schemes. We discuss the convergence of the whole approach, the implementation details and report the results of numerical experimentation on a set of large scale test problems arising from the discretization of elliptic control problems. A comparison with other interior point codes is also reported. This research was supported by the Italian Ministry for Education, University and Research (MIUR) projects: FIRB Project: “Parallel Nonlinear Numerical Optimization PN ² O” (grant n. RBAU01JYPN, ) and COFIN/PRIN04 Project “Numerical Methods and Mathematical Software for Applications” (grant n. 2004012559, ).     

Interior-Point Solver for Large-Scale Quadratic Programming Problems with Bound Constraints

In this paper, we present an interior-point algorithm for large and sparse convex quadratic programming problems with bound constraints. The algorithm is based on the potential reduction method and the use of iterative techniques to solve the linear system arising at each iteration. The global convergence properties of the potential reduction method are reassessed in order to take into account the inexact solution of the inner system. We describe the iterative solver, based on the conjugate gradient method with a limited-memory incomplete Cholesky factorization as preconditioner. Furthermore, we discuss some adaptive strategies for the fill-in and accuracy requirements that we use in solving the linear systems in order to avoid unnecessary inner iterations when the iterates are far from the solution. Finally, we present the results of numerical experiments carried out to verify the effectiveness of the proposed strategies. We consider randomly generated sparse problems without a special structure. Also, we compare the proposed algorithm with the MOSEK solver. Research partially supported by the MIUR FIRB Project RBNE01WBBB “Large-Scale Nonlinear Optimization.”     

Singular metrics and associated conformal groups underlying differential operators of mixed and degenerate types

For partial differential equations of mixed elliptic-hyperbolic and degenerate types which are the Euler-Lagrange equations for an associated Lagrangian, we examine an associated metric structure which becomes singular on the hypersurface where the operator degenerates. In particular, we show that the “non-trivial part” of the complete symmetry group for the differential operator (calculated in a previous paper by Lupo, D., Payne, K.R. [Conservation laws for equations of mixed elliptic-hyperbolic and degenerate types. Duke Math. J. [15]]) corresponds to a group of local conformal transformations with respect to the metric away from the metric singularity and that the group extends smoothly across the singular surface. In this way, we define and calculate the conformal group for these operators as well as for lower order singular perturbations which are defined naturally by the singular metric. Mathematics Subject Classification (2000) 35M10, 58J70, 53A30 Work supported by MIUR, Project “Metodi Variazionali ed Equazioni Differenziali Non Lineari” and MIUR, Project “Metodi Variazionali e Topologici nello Studio di Fenomeni Non Lineari”.     

Spurious Disambiguation Errors and How to Get Rid of Them

The disambiguation approach to the input of formulae enables users of mathematical assistants to type correct formulae in a terse syntax close to the usual ambiguous mathematical notation. When it comes to incorrect formulae however, far too many typing errors are generated; among them we want to present only errors related to the formula interpretation meant by the user, hiding errors related to other interpretations. We study disambiguation errors and how to classify them into the spurious and genuine error classes. To this end we give a general presentation of the classes of disambiguation algorithms and efficient disambiguation algorithms. We also quantitatively assess the quality of the presented error classification criteria benchmarking them in the setting of a formal development of constructive algebra. Partially supported by the Strategic Project “DAMA: Dimostrazione Assistita per la Matematica e l’Apprendimento” of the University of Bologna.     

Computational complexity of stable partitions with B-preferences

Consider a special stable partition problem in which the player's preferences over sets to which she could belong are identical with her preferences over the most attractive member of a set and in case of indifference the set of smaller cardinality is preferred. If the preferences of all players over other (individual) players are strict, a strongly stable and a stable partition always exists. However, if ties are present, we show that both the existence problems are NP-complete. These results are very similar to what is known for the stable roommates problem. Received: July 2000/Revised: October 2002 RID="*" ID="*"  This work was supported by the Slovak Agency for Science, contract #1/7465/20 “Combinatorial Structures and Complexity of Algorithms”.     

Scoring Unusual Words with Varying Mismatch Errors

Patterns consisting of strings with a bounded number of mismatches are central to coding theory and find multiple applications in text processing and computational biology. In this latter field, the presence of over-represented patterns of this kind has been linked, for instance, to modeling regulatory regions in biosequences. The study and computation of expected number of occurrences and related scores for these patterns is made difficult by the sheer explosion of the roster of candidates that need to be evaluated. In recent work, properties of pattern saturation and score monotonicity have proved capable to mitigate this problem. In such a context, expectation and score monotonicity has been established within the i.i.d. model for all cases of interest except that of a fixed word length with a varying number of mismatches. The present paper completes this investigation by showing that the expected number of occurrences in a textstring for such a word is bi-tonic, that is, behaves as a unimodal function of the number of errors. This extends to this case the time and space savings brought about by discovery algorithms based on pattern saturation. Work Supported in part by the Italian Ministry of University and Research under the Bi-National Project FIRB RBIN04BYZ7, and by the Research Program of Georgia Tech. An extended abstract related to this work was presented at the Dagstuhl Seminar Dagstuhl on “Combinatorial and Algorithmic Foundations of Pattern and Association Discovery”, May 14-19, 2006 [3].     

Multilevel decompositions of functional spaces

A unified abstract framework for the multilevel decomposition of both Banach and quasi-Banach spaces is presented. The characterization of intermediate spaces and their duals is derived from general Bernstein and Jackson inequalities. Applications to compactly supported biorthogonal wavelet decompositions of families of Besov spaces are also given. The first author was partially supported by grants from MURST (40% Analisi Numerica) and ASI (Contract ASI-92-RS-89), whereas the second author was partially supported by grants from MURST (40% Analisi Funzionale) and CNR (Progetto Strategico “Applicazioni della Matematica per la Tecnologia e la Società”).     

Ample subvarieties and rationally connected fibrations

Under some positivity assumptions, extension properties of rationally connected fibrations from a submanifold to its ambient variety are studied. Given a family of rational curves on a complex projective manifold X inducing a covering family on a submanifold Y with ample normal bundle in X, the main results relate, under suitable conditions, the associated rational connected fiber structures on X and on Y. Applications of these results include an extension theorem for Mori contractions of fiber type and a classification theorem in the case Y has a structure of projective bundle or quadric fibration. All authors acknowledge support by MIUR National Research Project “Geometry on Algebraic Varieties” (Cofin 2004). The research of the second author was partially supported by NSF grants DMS 0111298 and DMS 0548325. The third author acknowledges partial support by the University of Milan (FIRST 2003).     

On The Parameterized Intractability Of Motif Search Problems*

We show that Closest Substring, one of the most important problems in the field of consensus string analysis, is W[1]-hard when parameterized by the number k of input strings (and remains so, even over a binary alphabet). This is done by giving a “strongly structure-preserving” reduction from the graph problem Clique to Closest Substring. This problem is therefore unlikely to be solvable in time O(f(k)•n^c) for any function f of k and constant c independent of k, i.e., the combinatorial explosion seemingly inherent to this NP-hard problem cannot be restricted to parameter k. The problem can therefore be expected to be intractable, in any practical sense, for k ≥ 3. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, althoughb othp roblems are NP-complete. We also prove W[1]-hardness for other parameterizations in the case of unbounded alphabet size. Our W[1]-hardness result for Closest Substring generalizes to Consensus Patterns, a problem arising in computational biology. * An extended abstract of this paper was presented at the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002), Springer-Verlag, LNCS 2285, pages 262–273, held in Juan-Les-Pins, France, March 14–16, 2002. † Work was supported by the Deutsche Forschungsgemeinschaft (DFG), research project “OPAL” (optimal solutions for hard problems in computational biology), NI 369/2. ‡ Work was done while the author was with Wilhelm-Schickard-Institut für Informatik, Universit?t Tübingen. Work was partially supported by the Deutsche Forschungsgemeinschaft (DFG), Emmy Noether research group “PIAF” (fixed-parameter algorithms), NI 369/4.     

Regularity of minima: An invitation to the dark side of the calculus of variations

I am presenting a survey of regularity results for both minima of variational integrals, and solutions to non-linear elliptic, and sometimes parabolic, systems of partial differential equations. I will try to take the reader to the Dark Side... This work has been partially supported by MIUR via the project “Calcolo delle Variazioni” (Cofin 2004), and by GNAMPA via the project “Studio delle singolarità in problemi geometrici e variazionali”.     

Quadrature formulae with multiple nodes and a maximal trigonometric degree of exactness

In this paper we consider interpolatory quadrature formulae with multiple nodes, which have the maximal trigonometric degree of exactness. Our approach is based on a procedure given by Ghizzeti and Ossicini (Quadrature formulae, Academie-Verlag, Berlin, 1970). We introduce and consider the so-called σ-orthogonal trigonometric polynomials of semi-integer degree and give a numerical method for their construction. Also, some numerical examples are included. The authors were supported in part by the Serbian Ministry of Science and Technological Development (Project: Orthogonal Systems and Applications, grant number #144004) and the Swiss National Science Foundation (SCOPES Joint Research Project No. IB7320-111079 “New Methods for Quadrature”).     

An Identification Problem for First-Order Degenerate Differential Equations

We study a first-order identification problem in a Banach space. We discuss the nondegenerate and mainly the degenerate case. As a first step, suitable hypotheses on the involved closed linear operators are made in order to obtain unique solvability after reduction to a nondegenerate case; the general case is then handled with the help of new results on convolutions. Some applications to partial differential equations motivate this abstract approach.Communicated by I. GalliganiWork partially supported by MIUR (Ministero dell’ Istruzione, dell’ Università e dalla Ricerca), Project PRIN 2004011204 “Analisi Matematica nei Problemi Inversi,” and by the University of Bologna Funds for Selected Research Topics.     

Space structures: Theory and applications. 3

This paper is the third part of the book Space Structures: Theory and Applications. This part consists of an introduction and two chapters: “P²-Topological Spaces” and “Structured Sets.” __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 352, 2008, pp. 7–93.     

Some iterative methods for the solution of a symmetric indefinite KKT system

This paper is concerned with the numerical solution of a Karush–Kuhn–Tucker system. Such symmetric indefinite system arises when we solve a nonlinear programming problem by an Interior-Point (IP) approach. In this framework, we discuss the effectiveness of two inner iterative solvers: the method of multipliers and the preconditioned conjugate gradient method. We discuss the implementation details of these algorithms in an IP scheme and we report the results of a numerical comparison on a set of large scale test-problems arising from the discretization of elliptic control problems. This research was supported by the Italian Ministry for Education, University and Research (MIUR), FIRB Project RBAU01JYPN.     

Morse Index and Critical Groups for p-Laplace Equations with Critical Exponents

In this work we consider a class of Euler functionals defined in Banach spaces, associated to quasilinear elliptic problems involving the critical Sobolev exponent. We perform critical groups estimates via the Morse index. Dedicated to the memory of Professor Aldo Cossu The research of the authors was supported by the MIUR project “Variational and topological methods in the study of nonlinear phenomena” (PRIN 2005).     

Two Remarks Concerning Balanced Matroids

The property of balance (in the sense of Feder and Mihail) is investigated in the context of paving matroids. The following examples are exhibited: (a) a class of “sparse” paving matroids that are balanced, but at the same time rich enough combinatorially to permit the encoding of hard counting problems; and (b) a paving matroid that is not balanced. The computational significance of (a) is the following. As a consequence of balance, there is an efficient algorithm for approximating the number of bases of a sparse paving matroid within specified relative error. On the other hand, determining the number of bases exactly is likely to be computationally intractable. * The work described here was supported by the grant “Sharper analysis of randomised algorithms” from the UK Engineering and Physical Sciences Research Council.     

KAM Stability for a three-body problem of the Solar system

A new (iso-energetic) KAM method is tested on a specific three-body problem “extracted” from the Solar system (Sun-Jupiter + asteroid 12 Victoria). Analytical results in agreement with the observed data are established. This paper is a concise presentation of [2]. Supported by the MIUR projects: “Dynamical Systems: Classical, Quantum, Stochastic” and “Variational Methods and Nonlinear Differential Equations” Received: February 3, 2004     

Notes on a paper of Mess

These notes are a companion to the preceding paper by Geoffrey Mess, “Lorentz spacetimes of constant curvature”. Mess’ paper was written nearly 20 years ago and so we hope these notes will be useful as a guide to the literature that has appeared in the intervening years. Lars Andersson was supported in part by the NSF, contract no. DMS 0407732 and Thierry Barbot was supported by CNRS, ACI “Structures géométriques et Trous Noirs”.     

Reduced Vertex Set Result for Interval Semidefinite Optimization Problems

In this paper we propose a reduced vertex result for the robust solution of uncertain semidefinite optimization problems subject to interval uncertainty. If the number of decision variables is m and the size of the coefficient matrices in the linear matrix inequality constraints is n×n, a direct vertex approach would require satisfaction of 2 ^{n(m+1)(n+1)/2} vertex constraints: a huge number, even for small values of n and m. The conditions derived here are instead based on the introduction of m slack variables and a subset of vertex coefficient matrices of cardinality 2 ⁿ⁻¹, thus reducing the problem to a practically manageable size, at least for small n. A similar size reduction is also obtained for a class of problems with affinely dependent interval uncertainty. This work is supported by MIUR under the FIRB project “Learning, Randomization and Guaranteed Predictive Inference for Complex Uncertain Systems,” and by CNR RSTL funds.