Fuzzy statistics: regression and prediction

Our method of estimation of parameters in statistics uses a set of confidence intervals producing a triangular shaped fuzzy number for the estimator. In crisp linear regression we use this to obtain fuzzy number estimators for τ and λ. This is then employed in fuzzy prediction and fuzzy hypothesis testing about the values of τ and λ.     

On a quasiorder on the class of monounary algebras

In the paper we introduce a relation on the class of monounary algebras by means of -homomorphisms. It is a quasiorder. We take a subclass of containing monounary algebras satisfying the property We characterize algebras in by the notions of a degree and properties of their -endomorphisms. We apply the results to finite monounary algebras. Supported by grant VEGA 1/0161/03     

Approximation of 1/||x−y|| by Exponentials for Wavelet Applications (Short Communication)

We discuss the approximation of by exponentials in order to apply it to the treatmentof 1/||x-y||. In the case of a wavelet basis, one has in addition the vanishing moment property, which allows to add polynomials without increasing the computational effort. This leads to the question whether an approximation of by the sum of a polynomial and an exponential part yields an improvement. We show that indeed the approximation error is remarkably reduced. The improvement depends on the interval on which is approximated.     

The Fourier Finite-element Approximation of the Lamé Equations in Axisymmetric Domains with Edges

This paper is concerned with a priori error estimates and convergence analysis of the Fourier-finite-element solutions of the Neumann problem for the Lamé equations in axisymmetric domains with reentrant edges. The Fourier-FEM combines the approximating Fourier method with respect to the rotational angle using trigonometric polynomials of degree N (N→∞), with the finite element method on the plane meridian domain of with mesh size h (h→0) for approximating the Fourier coefficients. The asymptotic behavior of the solution near reentrant edges is described by singularity functions in non-tensor product form and treated numerically by means of finite element method on locally graded meshes. For the rate of convergence of the combined approximations in is proved to be of the order      

On the Crossing Number of Complete Graphs

Let (G) denote the rectilinear crossing number of a graph G. We determine (K₁₁)=102 and (K₁₂)=153. Despite the remarkable hunt for crossing numbers of the complete graph K_n – initiated by R. Guy in the 1960s – these quantities have been unknown forn>10 to date. Our solution mainly relies on a tailor-made method for enumerating all inequivalent sets of points (order types) of size 11. Based on these findings, we establish a new upper bound on (K_n) for general n. The bound stems from a novel construction of drawings of K_n with few crossings.     

Hierarchical Matrices Based on a Weak Admissibility Criterion

In preceding papers [8], [11], [12], [6], a class of matrices (-matrices) has been developed which are data-sparse and allow to approximate integral and more general nonlocal operators with almost linear complexity. In the present paper, a weaker admissibility condition is described which leads to a coarser partitioning of the hierarchical -matrix format. A coarser format yields smaller constants in the work and storage estimates and thus leads to a lower complexity of the -matrix arithmetic. On the other hand, it preserves the approximation power which is known in the case of the standard admissibility criterion. Furthermore, the new weak -matrix format allows to analyse the accuracy of the -matrix inversion and multiplication.     

Adaptive Geometrically Balanced Clustering of <Emphasis Type="Italic">H</Emphasis>-Matrices

In [8], a class of (data-sparse) hierarchical (-) matrices is introduced that can be used to efficiently assemble and store stiffness matrices arising in boundary element applications. In this paper, we develop and analyse modifications in the construction of an -matrix that will allow an efficient application to problems involving adaptive mesh refinement. In particular, we present a new clustering algorithm such that, when an -matrix has to be updated due to some adaptive grid refinement, the majority of the previously assembled matrix entries can be kept whereas only a few new entries resulting from the refinement have to be computed. We provide an efficient implementation of the necessary updates and prove for the resulting -matrix that the storage requirements as well as the complexity of the matrix-vector multiplication are almost linear, i.e., AMS Subject Classifications: 65F05, 65F30, 65N38, 65N50.     

Applications of -Matrix Techniques in Micromagnetics

The variational model by Landau and Lifshitz is frequently used in the simulation of stationary micromagnetic phenomena. We consider the limit case of large and soft magnetic bodies, treating the associated Maxwell equation exactly via an integral operator . In numerical simulations of the resulting minimization problem, difficulties arise due to the imposed side-constraint and the unboundedness of the domain. We introduce a possible discretization by a penalization strategy. Here the computation of is numerically the most challenging issue, as it leads to densely populated matrices. We show how an efficient treatment of both and the corresponding bilinear form can be achieved by application of -matrix techniques.     

Verification of Reduced Convergence Rates

In this short article, we recalculate the numerical example in Kíek and Neittaanmäki (1987) for the Poisson solution u=x(1–x)siny in the unit square S as . By the finite difference method, an error analysis for such a problem is given from our previous study by where h is the meshspacing of the uniform square grids used, and C₁ and C₂ are two positive constants. Let =u–u_h, where u_h is the finite difference solution, and is the discrete H¹ norm. Several techniques are employed to confirm the reduced rate of convergence, and to give the constants, C₁=0.09034 and C₂=0.002275 for a stripe domain. The better performance for arises from the fact that the constant C₁ is much large than C₂, and the h in computation is not small enough.     

Low-rank Kronecker-product Approximation to Multi-dimensional Nonlocal Operators. Part I. Separable Approximation of Multi-variate Functions

The Kronecker tensor-product approximation combined with the -matrix techniques provides an efficient tool to represent integral operators as well as certain functions F(A) of a discrete elliptic operator A in ℝ ^d with a high spatial dimension d. In particular, we approximate the functions A ⁻¹ and sign(A) of a finite difference discretisation A∈ℝ ^{N × N} with a rather general location of the spectrum. The asymptotic complexity of our data-sparse representations can be estimated by (n ^p log ^q n), p = 1, 2, with q independent of d, where n=N ^{1/ d} is the dimension of the discrete problem in one space direction. In this paper (Part I), we discuss several methods of a separable approximation of multi-variate functions. Such approximations provide the base for a tensor-product representation of operators. We discuss the asymptotically optimal sinc quadratures and sinc interpolation methods as well as the best approximations by exponential sums. These tools will be applied in Part II continuing this paper to the problems mentioned above.     

The Singular Sources Method for an Inverse Transmission Problem

We employ the singular sources method introduced in [4] to solve an inverse transmission scattering problem for the Helmholtz equation or D, respectively, where the total field u satisfies the transmission conditions on the boundary of some domain D with some constant β. The main idea of the singular sources scheme is to reconstruct the scattered field of point sources or higher multipoles (·, z) with source point z in its source point from the far field pattern of scattered plane waves. The function (z, z) is shown to become singular for z→∂D. This can be used to detect the shape D of the scattering object.Here, we will show how in addition to reconstructions of the shape D of the scattering object, the constant β can be reconstructed without solving the direct scattering problem. This extends the singular sources method from the reconstruction of geometric properties of an object to the reconstruction of physical quantities.     

Hierarchical Quadrature for Singular Integrals

We introduce a method for the computation of singular integrals arising in the discretization of integral equations. The basic method is based on the concept of admissible subdomains, known, e.g., from panel clustering techniques and -matrices: We split the domain of integration into a hierarchy of subdomains and perform standard quadrature on those subdomains that are amenable to it. By using additional properties of the integrand, we can significantly reduce the algorithmic complexity of our approach. The method works also well for hypersingular integrals.     

A Simplified Approach to the Order Conditions of Integration Methods

We present an approach to the numerical integration of ordinary differential equations based on the algebraic theory of Butcher (Math. Comp. 26, 79–106, 1972) and the -series theory of Hairer and Wanner (Computing 13, 1–15, 1974). We clarify the differences of these two approaches by equating the elementary weight functions and showing the differences of the composition rules. By interpreting the elementary weight function as a mapping from input values to output values and introducing some special mappings, we are able to derive the order conditions of several types of integration methods in a straight-forward way. The simplicity of the derivation is illustrated by linear multistep methods that use the second derivative as an input value, Runge-Kutta type methods that use the second as well as first derivatives, and general two-step Runge-Kutta methods. We derive new high stage-order methods in each example. In particular, we found a symmetric and stiffly-accurate method of order eight in the second example.     

Hierarchical Tensor-Product Approximation to the Inverse and Related Operators for High-Dimensional Elliptic Problems

The class of -matrices allows an approximate matrix arithmetic with almost linear complexity. In the present paper, we apply the -matrix technique combined with the Kronecker tensor-product approximation (cf. [2, 20]) to represent the inverse of a discrete elliptic operator in a hypercube (0, 1)^dd in the case of a high spatial dimension d. In this data-sparse format, we also represent the operator exponential, the fractional power of an elliptic operator as well as the solution operator of the matrix Lyapunov-Sylvester equation. The complexity of our approximations can be estimated by (dn log ^qn), where N=n^d is the discrete problem size.     

Asymptotic Fourier Coefficients for a C∞ Bell (Smoothed-“Top-Hat”) & the Fourier Extension Problem

In constructing local Fourier bases and in solving differential equations with nonperiodic solutions through Fourier spectral algorithms, it is necessary to solve the Fourier Extension Problem. This is the task of extending a nonperiodic function, defined on an interval , to a function which is periodic on the larger interval . We derive the asymptotic Fourier coefficients for an infinitely differentiable function which is one on an interval , identically zero for , and varies smoothly in between. Such smoothed “top-hat” functions are “bells” in wavelet theory. Our bell is (for x ≥ 0) where where . By applying steepest descents to approximate the coefficient integrals in the limit of large degree j, we show that when the width L is fixed, the Fourier cosine coefficients a _j of on are proportional to where Λ(j) is an oscillatory factor of degree given in the text. We also show that to minimize error in a Fourier series truncated after the Nth term, the width should be chosen to increase with N as . We derive similar asymptotics for the function f(x)=x as extended by a more sophisticated scheme with overlapping bells; this gives an even faster rate of Fourier convergence     

A 16-classification partition of formula set F(S) in revised Kleene system \bar W

This paper presents an exact expression of V(A) which is an unique formula A of formula set F(S) in revised Kleene system It also obtains a 16-classification congruence partition about unary operation ¬, combing with generalized tautology theory, and discusses each ones closeness about MP and HS operations.     

Translational lemmas for DLOGTIME-uniform circuits,alternating TMs,and PRAMs

We present translational lemmas for the three standard models of parallel computation, and apply them to obtain tight hierarchy results. It is shown that, for arbitrarily small rational constant , (i) there is a language which can be accepted by a -uniform circuit family of depth and size but not by any -uniform circuit family of depth and size , (ii) there is a language which can be accepted by a -time -space ATM with l worktapes but not by any -time -space ATM with the same l worktapes if the number of tape symbols is fixed, and (iii) there is a language which can be accepted by a -time PRAM with processors but not by any -time PRAM with processors. Here, c > 0, d ≥ 1, r ₁ > 1, and r ₂ ≥ 1 are arbitrary rational constants, and l ≥ 2 is an arbitrary integer. Preliminary versions of different parts of this paper appeared in Proc. MCU 2004 (LNCS 3354) and Proc. FCT 2005 (LNCS 3623).     

Preemptive and Non-preemptive On-line Algorithms for Scheduling with Rejection on Two Uniform Machines

In this paper, we consider the problem of on-line scheduling a job sequence on two uniform machines. A job can be either rejected, in which case we pay its penalty, or scheduled on machines, in which case it contributes its processing time to the makspan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule for all accepted jobs and the penalties of all rejected jobs. Both preemptive and non-preemptive versions are considered. For the preemptive version, we present an optimal on-line algorithm with a competitive ratio for any s≥1, where s is the machine speed ratio. For the non-preemptive version, we present an improved lower bound. Moreover, as an optimal algorithm for s≥1.6180 is known, we present a modified version of the known algorithm, and show that it becomes optimal for any 1.3852≤s<1.6180 and has a smaller competitive ratio than that of original version for any 1≤s<1.3852. The maximum gap between its competitive ratio and the lower bound is 0.0534.     

On the growth factor in Gaussian elimination for matrices with sharp angular field of values

Abstract Recently, the authors have shown that Gaussian elimination is stable for complex matrices A=B+iC where both B and C are Hermitian definite matrices. Moreover, the growth factor is less than under any diagonal pivoting order. Assume now that B and C, in addition to being (positive) definite, satisfy the inequality i.e., If = 0, then A = B is a Hermitian positive definite matrix. It is well-known that, in this case, the growth factor is equal to 1. For > 0, we establish a bound for the growth factor that has the limit 1 as 0.