Search

The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a non-negative monotone submodular function f:Z+n→R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of submodularity when the domain is the integer lattice. Given this, we design polynomial-time (1-1/e-ϵ)-approximation algorithms for a cardinality constraint, a polymatroid constraint, and a knapsack constraint. For a cardinality constraint, we also provide a (1-1/e-ϵ)-approximation algorithm with slightly worse time complexity that does not rely on the diminishing return property. [ABSTRACT FROM AUTHOR]

Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solution by solving a finite number of mixed-integer linear and continuous convex subproblems. The key advance we present is to strengthen the polyhedral approximations by constructing them in a higher-dimensional space. In order to automate this extended formulation we rely on the algebraic modeling technique of disciplined convex programming (DCP), and for generality and ease of implementation we use conic representations of the convex constraints. Although our framework requires a manual translation of existing models into DCP form, after performing this transformation on the MINLPLIB2 benchmark library we were able to solve a number of unsolved instances and on many other instances achieve superior performance compared with state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro. [ABSTRACT FROM AUTHOR]

The scheduling in grids is known to be a NP-hard problem. The distributed deployment of nodes, their heterogeneity and their fluctuations in terms of workload and availability make the design of an effective scheduling algorithm a very complex issue. The scientific literature has proposed several heuristics able to tackle this kind of optimization problem using techniques and strategies inspired by nature. The algorithms belonging to ant colony optimization (ACO) paradigm represent an example of these techniques: each one of these algorithms uses strategies inspired by the self-organization ability of real ants for building effective grid schedulers. In this paper, the authors propose an on line, non-clairvoyant, distributed scheduling solution for multi-broker grid based on the alienated ant algorithm (AAA), a new ACO inspired technique exploiting a 'non natural' behavior of ants and an inverse interpretation of pheromone trails. The paper introduces the proposed algorithm, explains the differences with other classical ACO approaches, and compares AAA with two different algorithms. The results of simulations show that the AAA guarantees good performance in terms of makespan, average queue waiting time and load balancing capability. [ABSTRACT FROM AUTHOR]

In this paper, we describe the BIBasis package designed for REDUCE and Macaulay2 computer algebra systems, which allows one to compute Boolean involutive bases and Gröbner bases. The implementations and user interfaces of the package for both systems are described in the respective sections of the paper. Also, we present results of comparisons of BIBasis with other packages and algorithms for constructing Boolean Gröbner bases available in the computer algebra systems. [ABSTRACT FROM AUTHOR]

Abstract  The study and research of evolutionary algorithms (EAs) is getting great attention in recent years. Although EAs have earned extensive acceptance through numerous successful applications in many fields, the problem of finding the best combination of evolutionary parameters especially for population size that need the manual settings by the user is still unresolved. In this paper, our system is focusing on differential evolution (DE) and its control parameters. To overcome the problem, two new systems were carried out for the self-adaptive population size to test two different methodologies (absolute encoding and relative encoding) in DE and compared their performances against the original DE. Fifty runs are conducted for every 20 well-known benchmark problems to test on every proposed algorithm in this paper to achieve the function optimization without explicit parameter tuning in DE. The empirical testing results showed that DE with self-adaptive population size using relative encoding performed well in terms of the average performance as well as stability compared to absolute encoding version as well as the original DE. [ABSTRACT FROM AUTHOR]

Let p be a prime, m ≥ 2, and ( m, p( p – 1)) = 1. In this paper, we will calculate explicitly the Gauss sum $$ G{\left( \chi \right)} = {\sum {_{{x \in \mathbb{F}^{ * }_{q} }} \chi {\left( x \right)}\zeta ^{{T{\left( x \right)}}}_{p} } } $$ in the case of [ (ℤ/ mℤ)* : 〈 p〉] = 4, and −1 ∉ 〈 p〉, where q = p f , $$ f = \frac{{\varphi {\left( m \right)}}} {4} $$ , χ is a multiplicative character of $${\Bbb F}$$ q with order m, and T is the trace map for $${\Bbb F}$$ q / $${\Bbb F}$$ p . Under the assumptions [ (ℤ/ mℤ)* : 〈 p〉] = 4 and −1 ∉ 〈 p〉, the decomposition field of p in the cyclotomic field ℚ(ζ m ) is an imaginary quartic (abelian) field. And G (χ) is an integer in K. We deal with the case where K is cyclic in this paper and leave the non–cyclic case to the next paper. [ABSTRACT FROM AUTHOR]

Global optimization problems are often approached by branch and bound algorithms which use linear relaxations of the nonlinear constraints computed from the current variable bounds. This paper studies how to derive safe linear relaxations to account for numerical errors arising when computing the linear coefficients. It first proposes two classes of safe linear estimators for univariate functions. Class-1 estimators generalize previously suggested estimators from quadratic to arbitrary functions, while class-2 estimators are novel. When they apply, class-2 estimators are shown to be tighter theoretically (in a certain sense) and almost always tighter numerically. The paper then generalizes these results to multivariate functions. It shows how to derive estimators for multivariate functions by combining univariate estimators derived for each variable independently. Moreover, the combination of tight class-1 safe univariate estimators is shown to be a tight class-1 safe multivariate estimator. Finally, multivariate class-2 estimators are shown to be theoretically tighter (in a certain sense) than multivariate class-1 estimators. [ABSTRACT FROM AUTHOR]

Finding the optimum distribution of material phases in a multi-material structure is a frequent and important problem in structural engineering which involves topology optimization. The Bi-directional Evolutionary Structural Optimization (BESO) method is now a well-known topology optimization method. In this paper an improved soft-kill BESO algorithm is introduced which can handle both single and multiple material distribution problems. A new filtering scheme and a gradual procedure inspired by the continuation approach are used in this algorithm. Capabilities of the proposed method are demonstrated using different examples. It is shown that the proposed method can result in considerable improvements compared to the normal BESO algorithm particularly when solving problems involving very soft material or void phase. [ABSTRACT FROM AUTHOR]

Biometric recognition systems have important roles in everyday activities. Online signature verification is one of the effective biometric solutions. Due to using dynamic characteristics of the online signature, it is more robust to copy problems. This paper presents a novel intra-class distance-based signature identification algorithm based on the combination of pressure and position features of an individual’s signature. In this algorithm, the pressure feature is combined with the position feature as a weight of the signature image that is called weighted signature image. By utilizing the Gabor filter on the weighted signature images, local features are extracted using a blocking scheme. Then, a distance-based strategy is employed for the signature identification process. In this strategy, the optimum decision boundary of the distance measure is selected based on the genuine and imposter intra-class distance density distribution functions. The proposed algorithm is evaluated on an SVC 2004 database containing 1,600 signatures from 40 different users. The obtained results show the effectiveness and efficiency of our algorithm in comparison with other common approaches. [ABSTRACT FROM AUTHOR]

In the paper, the Goursat problem-classification of nonlinear hyperbolic differential equations possessing two characteristic invariants-is considered. An algorithm for finding the characteristic invariants is described. On the basis of the algorithm implemented in REDUCE, the characteristic invariants of two Laine's equations are verified. One of them is shown to have invariants of the second and third orders. This equation shows that the Goursat problem, apparently, is still open. Computer calculations show that the characteristic invariants of the second Laine's equation given in his paper are incorrect. [ABSTRACT FROM AUTHOR]

An algorithm for finding the largest singular value of a nonnegative rectangular tensor was recently proposed by Chang, Qi, and Zhou [J. Math. Anal. Appl., 2010, 370: 284-294]. In this paper, we establish a linear convergence rate of the Chang-Qi-Zhou algorithm under a reasonable assumption. [ABSTRACT FROM AUTHOR]

Qualitative spatial representation and reasoning plays a important role in various spatial applications. In this paper we introduce a new formalism, we name RCD calculus, for qualitative spatial reasoning with cardinal direction relations between regions of the plane approximated by rectangles. We believe this calculus leads to an attractive balance between efficiency, simplicity and expressive power, which makes it adequate for spatial applications. We define a constraint algebra and we identify a convex tractable subalgebra allowing efficient reasoning with definite and imprecise knowledge about spatial configurations specified by qualitative constraint networks. For such tractable fragment, we propose several polynomial algorithms based on constraint satisfaction to solve the consistency and minimality problems. Some of them rely on a translation of qualitative networks of the RCD calculus to qualitative networks of the Interval or Rectangle Algebra, and back. We show that the consistency problem for convex networks can also be solved inside the RCD calculus, by applying a suitable adaptation of the path-consistency algorithm. However, path consistency can not be applied to obtain the minimal network, contrary to what happens in the convex fragment of the Rectangle Algebra. Finally, we partially analyze the complexity of the consistency problem when adding non-convex relations, showing that it becomes NP-complete in the cases considered. This analysis may contribute to find a maximal tractable subclass of the RCD calculus and of the Rectangle Algebra, which remains an open problem. [ABSTRACT FROM AUTHOR]

MAX-2-SAT is one of the representative combinatorial problems and is known to be NP-hard. Given a set of m clauses on n propositional variables, where each clause contains at most two literals and is weighted by a positive real, MAX-2-SAT asks to find a truth assignment that maximizes the total weight of satisfied clauses. In this paper, we propose branch-and-bound exact algorithms for MAX-2-SAT utilizing three kinds of lower bounds. All lower bounds are based on a directed graph that represents conflicts among clauses, and two of them use a set covering representation of MAX-2-SAT. Computational comparisons on benchmark instances disclose that these algorithms are highly effective in reducing the number of search tree nodes as well as the computation time. [ABSTRACT FROM AUTHOR]

In this paper, we study the strongly continuities, monotone autocontinuities of functions defined on effect algebras from above and below, respectively, we also present some examples to show that the autocontinuity, order continuity and monotone autocontinuity of functions defined on effect algebras are different each other. [ABSTRACT FROM AUTHOR]

In the paper we prove that the equational class $\mathcal{V}(bp\mathbb {BCK})$ generated by the class $bp\mathbb{BCK}$ of all bounded pseudo-BCK-algebras is generated by its simple members. As a matter of fact, we prove that simple members of $\mathcal {V}(bp\mathbb{BCK})$ just coincide with relative simple bounded pBCK-algebras. Moreover, as a byproduct we show that every simple bounded pBCK-algebra can be embedded into a simple integral residuated lattice. [ABSTRACT FROM AUTHOR]

In this paper, we present a simple method to prove the correctness and self-adjointness of operators B3 corresponding to some boundary problems. We also give the unique solutions for these problems. The algorithm is easy to implement via computer algebra systems. In our examples, Derive and Mathematica were used. Bibliography: 10 titles. [ABSTRACT FROM AUTHOR]

In the paper, an implementation in the computer algebra system Maple of an approach to summation based on hypergeometric pattern matching is considered. In spite of a number of existing modern summation algorithms, this approach remains to be valuable, since, if applicable, it allows one to find the result much faster than other approaches. The implementation is performed in the form of package Pattern Matching Summation. The structure of the package, pattern representation, possibility of extending the list of patterns, and matching mechanism are described. Examples of using the package are presented. Specific features of using summation formulas from handbooks as the patterns are considered. To obtain correct results, additional analysis is often required to determine the cases where the given formula is applicable. [ABSTRACT FROM AUTHOR]

The least-modules method allows one to process efficiently the data with anomalously great errors. The paper was devoted to the Weiszfeld algorithm enabling one to solve approximately the variational problem corresponding to the least-modules method. Estimates of nonoptimality of the algorithms’s iterations enabling one to estimate the quality of the approximate solution with anomalously great errors were obtained on the basis of the duality theory of the convex variational problems. [ABSTRACT FROM AUTHOR]

The crossed cube, which is a variation of the hypercube, possesses some properties that are superior to those of the hypercube. In this paper, we show that with the assumption of each node incident with at least two fault-free links, an n-dimensional crossed cube with up to 2 n−5 link faults can embed, with dilation one, fault-free cycles of lengths ranging from 4 to 2 n. The assumption is meaningful, for its occurrence probability is very close to 1, and the result is optimal with respect to the number of link faults tolerated. Consequently, it is very probable that algorithms executable on rings of lengths ranging from 4 to 2 n can be applied to an n-dimensional crossed cube with up to 2 n−5 link faults. [ABSTRACT FROM AUTHOR]

An important issue for solving multistage stochastic programs consists in the approximate representation of the (multivariate) stochastic input process in the form of a scenario tree. In this paper, we develop (stability) theory-based heuristics for generating scenario trees out of an initial set of scenarios. They are based on forward or backward algorithms for tree generation consisting of recursive scenario reduction and bundling steps. Conditions are established implying closeness of optimal values of the original process and its tree approximation, respectively, by relying on a recent stability result in Heitsch, Römisch and Strugarek (SIAM J Optim 17:511–525, 2006) for multistage stochastic programs. Numerical experience is reported for constructing multivariate scenario trees in electricity portfolio management. [ABSTRACT FROM AUTHOR]

An even factor in a digraph, introduced by Cunningham and Geelen (Vertex-disjoint dipaths and even dicircuits. manuscript, 2001), is a collection of vertex-disjoint dipaths and even dicycles, which generalizes a path-matching of Cunningham and Geelen (Combinatorica 17, 315–337, 1997). In a restricted class of digraphs, called odd-cycle-symmetric, Pap (Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, 3509, pp. 66–80, Springer, Heidelberg, 2005) presented a combinatorial algorithm to find a maximum even factor. For odd-cycle-symmetric weighted digraphs, which are odd-cycle-symmetric digraphs accompanied by a weight vector satisfying a certain property, Király and Makai (Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, 3064, pp. 416–430, Springer, Heidelberg, 2004) provided a linear program that describes the maximum weight even factor problem, and proved the dual integrality. In this paper, we present a primal-dual algorithm to find a maximum weight even factor for an odd-cycle-symmetric weighted digraph. This algorithm is based on the weighted matching algorithm of Edmonds and the maximum even factor algorithm of Pap. The running time of the algorithm is O( n 3 m), where n and m are the numbers of the vertices and arcs, respectively, which is better than that of the existing algorithms for the special cases. The algorithm also gives a constructive proof for the dual integrality. [ABSTRACT FROM AUTHOR]

Abstract   We study an online job scheduling problem arising in networks with aggregated links. The goal is to schedule n jobs, divided into k disjoint chains, on m identical machines, without preemption, so that the jobs within each chain complete in the order of release times and the maximum flow time is minimized. We present a deterministic online algorithm with competitive ratio , and show a matching lower bound, even for randomized algorithms. The performance bound for we derive in the paper is, in fact, more subtle than a standard competitive ratio bound, and it shows that in overload conditions (when many jobs are released in a short amount of time), ’s performance is close to the optimum. We also show how to compute an offline solution efficiently for k=1, and that minimizing the maximum flow time for k,m≥2 is -hard. As by-products of our method, we obtain two offline polynomial-time algorithms for minimizing makespan: an optimal algorithm for k=1, and a 2-approximation algorithm for any k. [ABSTRACT FROM AUTHOR]

In this paper we classify several algorithmic problems in group theory in the complexity classes PZK and SZK (problems with perfect/statistical zero-knowledge proofs respectively). Prior to this, these problems were known to be in $\mbox {\rm AM}\cap \mbox {\rm coAM}$ . As $\mbox {\rm PZK}\subseteq \mbox {\rm SZK}\subseteq \mbox {\rm AM}\cap \mbox {\rm coAM}$ , we have a tighter upper bound for these problems. Specifically: [ABSTRACT FROM AUTHOR]

This paper is intended as an attempt to describe logical consequence in branching time logics. We study temporal branching time logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ which use the standard operations Until and Next and dual operations Since and Previous (LTL, as standard, uses only Until and Next). Temporal logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ are generated by semantics based on Kripke/Hinttikka structures with linear frames of integer numbers $\mathcal {Z}$ with a single node (glued zeros). For $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ , the permissible branching of the node is limited by α (where 1≤ α≤ ω). We prove that any logic $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ is decidable w.r.t. admissible consecutions (inference rules), i.e. we find an algorithm recognizing consecutions admissible in $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ . As a consequence, it implies that $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ itself is decidable and solves the satisfiability problem. [ABSTRACT FROM AUTHOR]

Abstract  In this paper, we study the lattice structure of some fuzzy algebraic systems such as (G-)fuzzy groups, some fuzzy ordered algebras and fuzzy hyperstructures. We prove that under suitable conditions, these structures form a distributive or modular lattice. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to establish the second-order nonsmooth sufficient unconstrained optimality condition for so called ℓ-stable at some point functions and in this way to generalize some previous results in this direction. We provide the comparisons with other results by examples. [ABSTRACT FROM AUTHOR]

The paper considers the problem of computing zeros of scalar polynomials in several variables. The zeros of a polynomial are subdivided into the regular (eigen-and mixed) zeros and the singular ones. An algorithm for computing regular zeros, based on a decomposition of a given polynomial into a product of primitive polynomials, is suggested. The algorithm is applied to solving systems of nonlinear algebraic equations. Bibliography: 5 titles. [ABSTRACT FROM AUTHOR]

Abstract  The aim of this paper is to introduce the notion of fuzzy prime ideals of pseudo-MV algebras and investigate some of its properties. [ABSTRACT FROM AUTHOR]

The paper is an inquiry of the algebraic foundations of the theory of dispersionless integrable hierarchies, like the dispersionless KP and modified KP hierarchies and the universal Whitham hierarchy of genus zero. It stands out for the idea of interpreting these hierarchies as equations of coisotropic deformations for the structure constants of certain associative algebras. It discusses the link between the structure constants and Hirota’s tau function, and shows that the dispersionless Hirota bilinear equations are, within this approach, a way of writing the associativity conditions for the structure constants in terms of the tau function. It also suggests a simple interpretation of the algebro-geometric construction of the universal Whitham equations of genus zero due to Krichever. [ABSTRACT FROM AUTHOR]

We investigate a practical variant of the well-known graph Steiner tree problem. For a complete graph G = ( V, E ) with length function l: E → R + and two vertex subsets R ⊂ V and R ′ ⊆ R, a partial terminal Steiner tree is a Steiner tree which contains all vertices in R such that all vertices in R ∖ R ′ belong to the leaves of this Steiner tree. The partial terminal Steiner tree problem is to find a partial terminal Steiner tree T whose total lengths ∑ (u,v ) ∈T l ( u, v ) is minimum. In this paper, we show that the problem is both NP-complete and MAX SNP-hard when the lengths of edges are restricted to either 1 or 2. We also provide an approximation algorithm for the problem. [ABSTRACT FROM AUTHOR]

The goal of computational homogenization is to obtain the macro-scale response, normally in terms of macro-scale stress for given macro-scale deformation, via RVE-computations. In this paper we investigate, in a systematic manner, the effects of Dirichlet and Neumann boundary conditions on the RVE. Adaptive computations are carried out with respect to, in particular, control of the error in the macro-scale stress tensor. This requires the corresponding dual solutions. As a new result, it is shown how the same dual solutions can be conveniently used in computing the algorithmic tangent stiffness tensor, thereby demonstrating the “power of duality”. [ABSTRACT FROM AUTHOR]

The paper continues the development of rank-factorization methods for solving certain algebraic problems for multi-parameter polynomial matrices and introduces a new rank factorization of a q-parameter polynomial m × n matrix F of full row rank (called the PG-q factorization) of the form F = PG, where $$P = \prod\limits_{k = 1}^{q - 1} {\prod\limits_{i = 1}^{n_k } {\nabla _i^{(k)} } } $$ is the greatest left divisor of F; Δ i is a regular (q-k)-parameter polynomial matrix the characteristic polynomial of which is a primitive polynomial over the ring of polynomials in q-k-1 variables, and G is a q-parameter polynomial matrix of rank m. The PG-q algorithm is suggested, and its applications to solving some problems of algebra are presented. Bibliography: 6 titles. [ABSTRACT FROM AUTHOR]

An algebra A is said to be congruence permutable if any two congruences on it are permutable. This property has been investigated in several varieties of algebras, for example, de Morgan algebras, p-algebras, Kn,o-algebras. In this paper, we study the class of symmetric extended de Morgan algebras that are congruence permutable. In particular we consider the case where A is finite, and show that A is congruence permutable if and only if it is isomorphic to a direct product of finitely many simple algebras. [ABSTRACT FROM AUTHOR]

In this paper, we present necessary optimality conditions for nondifferentiable minimax fractional programming problems. A new concept of generalized convexity, called (C, α, ρ d)-convexity, is introduced. We establish also sufficient optimality conditions for nondifferentiable minimax fractional programming problems from the viewpoint of the new generalized convexity. When the sufficient conditions are utilized, the corresponding duality theorems are derived for two types of dual programs. [ABSTRACT FROM AUTHOR]

In this paper, we offer a graded equivalence between the quotient categories defined by any graded Morita–Takeuchi context via certain modifications of the graded cotensor functors. As a consequence, we show a commutative diagram that establish the relation between the closed objects of the categories gr C and M C , where C is a graded coalgebra. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the expected number of steps in solving multi–discrete logarithm problems over a group of elliptic curves with prime order by using Pollard's rho method and parallel collision search algorithm. We prove that when using these algorithms to compute discrete logarithms, the knowledge gained through computing many logarithms does not make it easier for finding other logarithms. Hence in an elliptic cryptosystem, it is safe for many users to share the same curve, with different private keys. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithm to identify the occurrence of impact (contact) among structures. Structures are modeled here by finite elements and the resulting formulation is employed to solve two-dimensional frame impact problems by the Lagrange Multiplier technique. The proposed algorithm is based on potential theory, largely employed in various fields of physics. The potential theory is used together with integral equations making possible to compare relative positions among nodes of different structures involved in a collision process. The present technique may be used to model the contact prevision among two or three-dimensional structures or between structures and rigid obstacles. In order to show the applicability of the proposed technique, numerical answers for 2D problems are compared with both analytical solutions and numerical results given by other authors. [ABSTRACT FROM AUTHOR]

Let G be a connected reductive algebraic group over an algebraically closed field k of characteristic p≥0, and 𝔤=Lie G. In positive characteristic, suppose in addition that p is good for G and the derived subgroup of G is simply connected. Let 𝒩=𝒩(𝔤) denote the nilpotent variety of 𝔤, and ℭnil(𝔤):={(x,y)∈𝒩×𝒩 | [x,y]=0}, the nilpotent commuting variety of 𝔤. Our main goal in this paper is to show that the variety ℭnil(𝔤) is equidimensional. In characteristic 0, this confirms a conjecture of Vladimir Baranovsky; see [2]. When applied to GL(n), our result in conjunction with an observation in [2] shows that the punctual (local) Hilbert scheme ℋn⊂Hilbn(ℙ2) is irreducible over any algebraically closed field. [ABSTRACT FROM AUTHOR]

Consider a classical cusp eigenform f=∑n=1∞an(f)qn of weight k≥2 for Γ0(N) with a Dirichlet character ψ mod N, and let Lf(s,χ)=∑n=1∞χ(n)an(f)n-s denote the L-function of f twisted with an arbitrary Dirichlet character χ. For a prime number p≥5, consider a family of cusp eigenforms f(k′) of weight k′, k′↦{f(k′)= ∑n=1∞an(f(k′))qn} containing f=f(k), such that the Fourier coefficients an(f(k′)) are given by certain p-adic analytic functions k′↦an(f(k′)). The purpose of this paper is to construct a two variable p-adic L function attached to Coleman’s family {f(k′)} of cusp eigenforms of a fixed positive slope σ=vp(αp)>0 where αp=αp(k′) is an eigenvalue (which depends on k′) of the Atkin operator U=Up. Our p-adic L-function interpolates the special values Lf(k′)(s,χ) at points (s,k′) with s=1,2,...,k′-1. We give a construction using the Rankin-Selberg method and the theory of p-adic integration on a profinite group Y with values in an affinoid K-algebra A, where K is a fixed finite extension of Qp. Our p-adic L-functions are p-adic Mellin transforms of certain A-valued measures. In their turn, such measures come from Eisenstein distributions with values in certain Banach A-modules M†=M†(N;A) of families of overconvergent forms over A. [ABSTRACT FROM AUTHOR]

Many characterizations of semipreconnected (=β-connected) spaces are obtained by Aho and Nieminen [2]. In this paper, we obtain further characterizations of semipreconnected spaces. We introduce β-separated and βs-connected sets and by using these sets we obtain several properties of β-connected subspaces. [ABSTRACT FROM AUTHOR]

Effective design of parallel matrix multiplication algorithms relies on the consideration of many interdependent issues based on the underlying parallel machine or network upon which such algorithms will be implemented, as well as, the type of methodology utilized by an algorithm. In this paper, we determine the parallel complexity of multiplying two (not necessarily square) matrices on parallel distributed-memory machines and/or networks. In other words, we provided an achievable parallel run-time that can not be beaten by any algorithm (known or unknown) for solving this problem. In addition, any algorithm that claims to be optimal must attain this run-time. In order to obtain results that are general and useful throughout a span of machines, we base our results on the well-known LogP model. Furthermore, three important criteria must be considered in order to determine the running time of a parallel algorithm; namely, (i) local computational tasks, (ii) the initial data layout, and (iii) the communication schedule. We provide optimality results by first proving general lower bounds on parallel run-time. These lower bounds lead to significant insights on (i)–(iii) above. In particular, we present what types of data layouts and communication schedules are needed in order to obtain optimal run-times. We prove that no one data layout can achieve optimal running times for all cases. Instead, optimal layouts depend on the dimensions of each matrix, and on the number of processors. Lastly, optimal algorithms are provided. [ABSTRACT FROM AUTHOR]

In this paper, a new parallel algorithm for solving parabolic equations is proposed. The new algorithm includes two domain decomposition methods, each method is applied to compute the values at (n+1)st time level by use of known numerical solutions at nth time level, respectively. Then the average of two above values is chosen to be the numerical solutions at (n+1)st time level. The new algorithm obtains satisfactory accuracy while maintaining parallelism and unconditional stability. This algorithm can be extended to solve two-dimensional parabolic equations by alternating direction implicit (ADI) technique. Both error analysis and numerical experiments illustrate the accuracy and efficiency of the new algorithm. [ABSTRACT FROM AUTHOR]