The updating technique for the solution of a sequence of linear equations

In this paper we will present and analyze an algorithm for solving a sequence of linear equations of the form \(\left( {A + \lambda _i B} \right)x = b,i = 1,2,...,r,\) wherex, b∈R ⁿ , andA, B aren x n real dense and large matrices. Two matrix factorizations are suggested that will allow efficient updating by changing λ _i . They are recommended ifB is singular or ill-conditioned. The implementation cost is evaluated and numerical results are included to present the performance of the two factorizations and in the solution of the above sequence of equations.     

Effective condition number and its applications

Consider the over-determined system Fx = b where ${{\bf F}\in\mathcal{R}^{m \times n}, m \geq n}$ and rank (F) = r ≤ n, the effective condition number is defined by ${{\rm Cond_{-}eff }= \frac {\|{\bf b}\|}{\sigma_r\|{\bf x}\|}}$ , where the singular values of F are given as σ _max = σ ₁ ≥ σ ₂ ≥ . . . ≥ σ _r > 0 and σ _r+1 = . . . = σ _n = 0. For the general perturbed system (A+ΔA)(x+Δx) = b+Δb involving both ΔA and Δb, the new error bounds pertinent to Cond_eff are derived. Next, we apply the effective condition number to the solutions of Motz’s problem by the collocation Trefftz methods (CTM). Motz’s problem is the benchmark of singularity problems. We choose the general particular solutions ${v_L = \sum\nolimits_{k=0}^L d_k (\frac {r}{R_p})^{k+\frac 12}}$ ${{\rm cos}(k +\frac 12)\theta}$ with a radius parameter R _p . The CTM is used to seek the coefficients d _i by satisfying the boundary conditions only. Based on the new effective condition number, the optimal parameter R _p = 1 is found. which is completely in accordance with the numerical results. However, if based on the traditional condition number Cond, the optimal choice of R _p is misleading. Under the optimal choice R _p = 1, the Cond grows exponentially as L increases, but Cond_eff is only linear. The smaller effective condition number explains well the very accurate solutions obtained. The error analysis in [14,15] and the stability analysis in this paper grant the CTM to become the most efficient and competent boundary method.     

Adaptive quadratures over volumes

We consider the numerical approximation of volume integrals over bounded domainsD:={D∈R ³:H(x>≤0}, whereH:R ³→R is a suitable decidability function. The integrands may be smooth maps or singular maps such as those arising in the volume potentials for boundary integral methods. An adaptive extrapolation method is described which is based on some simple quadrature rules. It utilizes an automatic simplicial subdivision of the domain. The method offers improvements over recently given approaches. A special version is offered for the important application of the numerical computation of volume potentials in boundary integral methods. Several examples illustrate the performance of the method.     

On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs

Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply forwarded to a neighbor that is closer to the destination. It has been an open conjecture whether every 3-connected plane graph has a greedy drawing in the Euclidean plane R ² (by Papadimitriou and Ratajczak in Theor. Comp. Sci. 344(1):3–14, 2005). Leighton and Moitra (Discrete Comput. Geom. 44(3):686–705, 2010) recently settled this conjecture positively. One main drawback of this approach is that the coordinates of the virtual locations require Ω(nlogn) bits to represent (the same space usage as traditional routing table approaches). This makes greedy routing infeasible in applications. In this paper, we show that the classical Schnyder drawing in R ² of plane triangulations is greedy with respect to a simple natural metric function H(u,v) over R ² that is equivalent to Euclidean metric D _E (u,v) (in the sense that $D_{E}(u,v) \leq H(u,v) \leq2\sqrt{2}D_{E}(u,v)$ ). The drawing uses two integer coordinates between 0 and 2n?5, which can be represented by logn bits. We also show that the classical Schnyder drawing in R ² of 3-connected plane graphs is weakly greedy with respect to the same metric function H(?,?). The drawing uses two integer coordinates between 0 and f (where f is the number of internal faces of G).     

PP-Lowness and a Simple Definition of AWPP

Abstract. We show that the counting classes AWPP and APP [FFKL], [L] are more robust than previously thought. Our results identify a sufficient condition for a language to be low for PP, and we show that this condition is at least as weak as other previously studied criteria. We extend a result of Köbler et al. by proving that all sparse co-C ₌ P languages are in APP, and are thus PP-low. Our results also imply that AWPP ?eq APP, and thus APP contains many other established subclasses of PP-low, thereby reducing several different lowness results to membership in APP. We also show that AWPP and APP are Σ ⁰ ₂ -definable classes. Some of our results are reminiscent of amplifying certainty in probabilistic computation.     

A note on balanced immunity

For a finite alphabet ∑ we define a binary relation on \(2^{\Sigma *} \times 2^{2^{\Sigma ^* } } \) , called balanced immunity. A setB ? ∑* is said to be balancedC-immune (with respect to a classC ? 2^Σ* of sets) iff, for all infiniteL εC, $$\mathop {\lim }\limits_{n \to \infty } \left| {L^{ \leqslant n} \cap B} \right|/\left| {L^{ \leqslant n} } \right| = \tfrac{1}{2}$$ Balanced immunity implies bi-immunity and in natural cases randomness. We give a general method to find a balanced immune set'B for any countable classC and prove that, fors(n) =o(t(n)) andt(n) >n, there is aB εSPACE(t(n)), which is balanced immune forSPACE(s(n)), both in the deterministic and nondeterministic case.     

Local noncuppability in R/M

Given any [c], [a], [d] xxxxxxxxR/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] xxxxxxxxR/M such that [d] ≤ [b] < [c]. It will be shown that given any nonzero [c] xxxxxxxxR/M, there are [a], [d] xxxxxxxxR/M such that [d] < [a] ≤ [c] and [a] is locally noncuppable between [c] and [d].     

Bisection forAx=λBx with matrices of variable band width

Some extensions of the bisection method and of the inverse vector iteration for the general eigenvalue problemAx=λBx with symmetric matrices are given. A version with restricted pivoting is applied to sparse matricesA andB in which case the decomposition ofA-μB can be performed within an extended envelope with respect to the envelopeA andB. The effect of these refinements is illustrated by an example.     

A sound and complete R-calculi with respect to contraction and minimal change

AGM postulates are for belief revision (revision by a single belief), and DP postulates are for iterated revision (revision by a finite sequence of beliefs). R-calculus is given for R-configurations Δ|Γ, where Δ is a set of atomic formulas or the negations of atomic formulas, and Γ is a finite set of formulas. We shall give two R-calculi C and M (sets of deduction rules) such that for any finite consistent sets Γ, Δ of formulas in the propositional logic, there is a consistent set Θ ? Γ of formulas such that Δ|Γ ? Δ, Θ is provable and Θ is a contraction of Γ by Δ or a minimal change of Γ by Δ; and prove that C and M are sound and complete with respect to the contraction and the minimal change, respectively.     

Attracting ellipsoids and synthesis of oscillatory regimes

An approach to stabilization of nonlinear oscillations in multidimensional spaces is proposed on the basis of the V.I. Zubov’s stability theory for invariant sets. As a special case, the derived controls make it possible to excite self-oscillating regimes in specified state subspaces R ^2k ? R ²ⁿ with simultaneous oscillation damping on Cartesian products R ^2n?2k .     

Minimum Manhattan Network Problem in Normed Planes with Polygonal Balls: A Factor 2.5 Approximation Algorithm

Let ${\mathcal{B}}$ be a centrally symmetric convex polygon of ?² and ‖p?q‖ be the distance between two points p,q∈?² in the normed plane whose unit ball is ${\mathcal{B}}$ . For a set T of n points (terminals) in ?², a ${\mathcal{B}}$ -network on T is a network N(T)=(V,E) with the property that its edges are parallel to the directions of ${\mathcal{B}}$ and for every pair of terminals t _i and t _j , the network N(T) contains a shortest ${\mathcal{B}}$ -path between them, i.e., a path of length ‖t _i ?t _j ‖. A minimum ${\mathcal{B}}$ -network on T is a ${\mathcal{B}}$ -network of minimum possible length. The problem of finding minimum ${\mathcal{B}}$ -networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX’99) in the case when the unit ball ${\mathcal{B}}$ is a square (and hence the distance ‖p?q‖ is the l ₁ or the l _∞-distance between p and q) and it has been shown recently by Chin, Guo, and Sun (Symposium on Computational Geometry, pp. 393–402, 2009) to be strongly NP-complete. Several approximation algorithms (with factors 8, 4, 3, and 2) for the minimum Manhattan problem are known. In this paper, we propose a factor 2.5 approximation algorithm for the minimum ${\mathcal{B}}$ -network problem. The algorithm employs a simplified version of the strip-staircase decomposition proposed in our paper (Chepoi et al. in Theor. Comput. Sci. 390:56–69, 2008, and APPROX-RANDOM, pp. 40–51, 2005) and subsequently used in other factor 2 approximation algorithms for the minimum Manhattan problem.     

On relativizing auxiliary pushdown machines

We consider relativizing the constructions of Cook in [4] characterizing space-bounded auxiliary pushdown automata in terms of timebounded computers. LetS(n) ≥ logn be a measurable space bound. LetDT ^A[NT^A] be the class of setsS such that there exists a machineM such thatM with oracleA recognizes the setS andM is a deterministic [nondeterministic] oracle Turing machine acceptor that runs in time 2 ^cS(n) for some constantc. LetDB _i ^A [NB _i ^A ] be the class of setsS such that there exists a machineM such thatM with oracleA recognizes the setS andM is a deterministic [non-deterministic] oracle Turing machine acceptor with auxiliary pushdown that runs in spaceS(n) and never queries the oracle about strings longer than:S(n) ifi = 1, 2 ^cS(n) for some constantc, ifi = 2, + ∞ ifi = 3. Then we prove the following results: These contrast with Cook's (unrelativized) result:DT = NB = DB.     

Iterations for solving linear variational inequalities on domains with nonlinear boundaries

This paper deals with numerical methods for solving linear variational inequalities on an arbitrary closed convex subsetC of ? ⁿ . Although there were numerous iterations studied for the caseC=? ₊ ⁿ , few were proposed for the case whenC is a closed convex subset. The essential difficulty in this case is the nonlinearities ofC's boundaries. In this paper iteration processes are designed for solving linear variational inequalities on an arbitrary closed convex subsetC. In our algorithms the computation of a linear variational inequality is decomposed into a sequence of problems of projecting a vector to the closed convex subsetC, which are computable as long as the equations describing the boundaries are given. In particular, using our iterations one can easily compute a solution whenC is one of the common closed convex subsets such as cube, ball, ellipsoid, etc. The non-accurate iteration, the estimate of the solutions on unbounded domains and the theory of approximating the boundaries are also established. Moreover, a necessary and sufficient condition is given for a vector to be an approximate solution. Finally, some numerical examples are presented, which show that the designed algorithms are effective and efficient. The exposition of this paper is self-contained.     

Crystal: Integrating Structured Queries into a Tactic Language

We present the language CRStL (Control Rule Strategy Language, pronounce “crystal”) to formulate mathematical reasoning techniques as proof strategies in the context of the proof assistant Ωmega. The language is arranged in two levels, a query language to access mathematical knowledge maintained in development graphs, and a strategy language to annotate the results of these queries with further control information. The two-leveled structure of the language allows the specification of proof techniques in a declarative way. We present the syntax and semantics of CRStL and illustrate its use by examples.     

A finite element to interpolate symmetric tensors with divergence inL 2

Inner approximations of the space of second order symmetric tensors with square-integrable «divergence» over a bounded domain inR ² are built up by means of a family of affine elements, analogous to the family defined by Raviart and Thomas in the case of vectors. As an application, we solve the Dirichlet problem for the biharmonic operator by a method of «equilibrium» type.     

Average time behavior of distributive sorting algorithms

In this paper we investigate the expected complexityE(C) of distributive (“bucket”) sorting algorithms on a sampleX ₁, ...,X _n drawn from a densityf onR ¹. Assuming constant time bucket membership determination and assuming the use of an average timeg(n) algorithm for subsequent sorting within each bucket (whereg is convex,g(n)/n↑∞,g(n)/n ² is nonincreasing andg is independent off), the following is shown:

1. Iff has compact support, then ∫g(f(x))dx<∞ if and only ifE(C)=0(n).
2. Iff does not have compact support, then \(E(C)/n\xrightarrow{n}\infty \) .

No additional restrictions are put onf.     

The Parallel Complexity of Graph Canonization Under Abelian Group Action

We study the problem of computing canonical forms for graphs and hypergraphs under Abelian group action and show tight complexity bounds. Our approach is algebraic. We transform the problem of computing canonical forms for graphs to the problem of computing canonical forms for associated algebraic structures, and we develop parallel algorithms for these associated problems.

1. In our first result we show that the problem of computing canonical labelings for hypergraphs of color class size 2 is logspace Turing equivalent to solving a system of linear equations over the field $\mathbb {F} _{2}$ . This implies a deterministic NC ² algorithm for the problem.
2. Similarly, we show that the problem of canonical labeling graphs and hypergraphs under arbitrary Abelian permutation group action is fairly well characterized by the problem of computing the integer determinant. In particular, this yields deterministic NC ³ and randomized NC ² algorithms for the problem.

     

The Equivalence of Sampling and Searching

In a sampling problem, we are given an input x∈{0,1} ⁿ , and asked to sample approximately from a probability distribution \(\mathcal{D}_{x}\) over \(\operatorname{poly} ( n ) \) -bit strings. In a search problem, we are given an input x∈{0,1} ⁿ , and asked to find a member of a nonempty set A _x with high probability. (An example is finding a Nash equilibrium.) In this paper, we use tools from Kolmogorov complexity to show that sampling and search problems are “essentially equivalent.” More precisely, for any sampling problem S, there exists a search problem R _S such that, if \(\mathcal{C}\) is any “reasonable” complexity class, then R _S is in the search version of \(\mathcal{C}\) if and only if S is in the sampling version. What makes this nontrivial is that the same R _S works for every  \(\mathcal{C}\) . As an application, we prove the surprising result that SampP=SampBQP if and only if FBPP=FBQP. In other words, classical computers can efficiently sample the output distribution of every quantum circuit, if and only if they can efficiently solve every search problem that quantum computers can solve.     

Contraction-Free Linear Depth Sequent Calculi for Intuitionistic Propositional Logic with the Subformula Property and Minimal Depth Counter-Models

In this paper we present LSJ, a contraction-free sequent calculus for Intuitionistic propositional logic whose proofs are linearly bounded in the length of the formula to be proved and satisfy the subformula property. We also introduce a sequent calculus RJ for intuitionistic unprovability with the same properties of LSJ. We show that from a refutation of RJ of a sequent σ we can extract a Kripke counter-model for σ. Finally, we provide a procedure that given a sequent σ returns either a proof of σ in LSJ or a refutation in RJ such that the extracted counter-model is of minimal depth.     

A simple band ratio technique to quantify the colored dissolved and detrital organic material from ocean color remotely sensed data

Spectral reflectances of the ocean, R, as derived from ocean color remote sensing data at four wavelengths (412, 443, 490, and 555 nm), can be used to form two ratios of spectral reflectance, namely R(412)/R(443), and R(490)/R(555), thereafter denoted R₄₄₃⁴¹² and R₅₅₅⁴⁹⁰. The former is mainly sensitive to the colored dissolved organic material (CDOM), albeit influenced by the algal content as depicted by the chlorophyll concentration, ([Chl]); in contrast, the latter is essentially depending on [Chl], although it is also influenced by CDOM. Therefore the signatures of CDOM and [Chl] which are not truly separable, can nevertheless be identified by considering simultaneously the two ratios. The concomitant variations in these ratios can be established via a bio-optical model developed for Case 1 waters. This model implicitly includes a “mean” relationship between CDOM and [Chl], and thus produces a unique curve relating R₄₄₃⁴¹² to R₅₅₅⁴⁹⁰. Deviations with respect to this mean relationship can be introduced through a factor Φ, with Φ > 1 (excess) or < 1 (deficit), applied to the CDOM-[Chl] ratio. A family of R₄₄₃⁴¹²-R₅₅₅⁴⁹⁰ curves is thus generated, in correspondence with the discrete values given to Φ; this “grid” (or numerically, a 2-D lookup table) allows the Φ-[Chl] couple to be unambiguously derived for any R₄₄₃⁴¹²-R₅₅₅⁴⁹⁰ couple. By applying this straightforward algorithm to actual reflectance ratios derived from ocean color imagery, the relative anomalies in CDOM with respect to its standard (Chl-related) values can be efficiently assessed. Within the global ocean (discarding the coastal zones), the Φ factor is widely varying, between at least ? and 3, and is roughly log-normally distributed around ~ 1 (no anomaly). The spatial distributions of the Φ factor in the whole ocean are strongly featured according to latitude, season, and hydrographic regimes, and these features are regularly reproducible, from year to year (2002-2007). This simple method is also validated against available in situ data, and its results compare favorably, for instance, to those of the GSM (Garver-Siegel-Maritorena) inversion method, in terms of retrieved CDOM concentrations and distribution patterns.