Auxiliary function | EPFL Graph Search

In mathematics, auxiliary functions are an important construction in transcendental number theory. They are functions that appear in most proofs in this area of mathematics and that have specific, desirable properties, such as taking the value zero for many arguments, or having a zero of high order at some point. Definition Auxiliary functions are not a rigorously defined kind of function, rather they are functions which are either explicitly constructed or at least shown to exist and which provide a contradiction to some assumed hypothesis, or otherwise prove the result in question. Creating a function during the course of a proof in order to prove the result is not a technique exclusive to transcendence theory, but the term "auxiliary function" usually refers to the functions created in this area. Explicit functions Liouville's transcendence criterion Because of the naming convention mentioned above, auxiliary functions can be dated back to their so

A Dichotomy for Real Weighted Holant Problems

Sangxia Huang

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as the counting constraint satisfaction problem (#CSP) and graph homomorphism. An effective dichotomy for such frameworks can immediately settle the complexity of all combinatorial problems expressible in that framework. Both #CSP and graph homomorphism can be viewed as subfamilies of Holant with the additional assumption that the equality constraints are always available. Other subfamilies of Holant such as Holant() and Holant (c) problems, in which we assume some specific sets of constraints to be freely available, were also studied. The Holant framework becomes more expressive and contains more interesting tractable cases with less or no freely available constraint functions, while, on the other hand, it also becomes more challenging to obtain a complete characterization of its time complexity. Recently, a complexity dichotomy for a variety of subfamilies of Holant such as #CSP, graph homomorphism, Holant(), and Holant (c) for Boolean domain was proved. In this paper, we prove a dichotomy for the general Holant framework where all the constraints are real symmetric functions on Boolean inputs. This setting already captures most of the interesting combinatorial counting problems defined by local constraints, such as (perfect) matching. This is the first time a dichotomy is obtained for general Holant problems without any auxiliary functions. One benefit of working with the Holant framework is some powerful new reduction technique such as the holographic reduction. Along the proof of our dichotomy, we introduce a new reduction technique, namely realizing a constraint function by approximating it. This new technique is employed in our proof in a situation where it seems that all previous reduction techniques fail; thus, this new idea of reduction might also be of independent interest. Besides proving a dichotomy and developing a new technique, we also obtained some interesting by-products. We prove a dichotomy for #CSP, restricting to instances where each variable appears a multiple of d times for any d. We also prove that counting the number of Eulerian orientations on 2k-regular graphs is #P-hard for any .

Springer Basel Ag2016

Local nonreflecting boundary condition for time-dependent multiple scattering

Imbo Sim

Starting from from a high-order local nonreflecting boundary condition (NBC) for single scattering [25], we derive a local NBC for time-dependent multiple scattering problems in three space dimensions, which is completely local both in space and time. To do so, we first develop an exterior evaluation formula for a purely outgoing wave field, given its values and those of certain auxiliary functions needed for the local NBC at the artificial boundary. By combining that evaluation formula with the decomposition of the total scattered field into purely outgoing contributions, we obtain a completely local NBC for time-dependent multiple scattering problems. The accuracy and stability of this new local NBC are evaluated by coupling it to a standard finite difference method. (C) 2011 Elsevier Inc. All rights reserved.

2011

hm-toolbox: Matlab software for HODLR and HSS matrices

Daniel Kressner, Stefano Massei

Matrices with hierarchical low-rank structure, including HODLR and HSS matrices, constitute a versatile tool to develop fast algorithms for addressing large-scale problems. While existing software packages for such matrices often focus on linear systems, their scope of applications is in fact much wider and includes, for example, matrix functions and eigenvalue problems. In this work, we present a new Matlab toolbox called hm-toolbox, which encompasses this versatility with a broad set of tools for HODLR and HSS matrices, unmatched by existing software. While mostly based on algorithms that can be found in the literature, our toolbox also contains a few new algorithms as well as novel auxiliary functions. Being entirely based on Matlab, our implementation does not strive for optimal performance. Nevertheless, it maintains the favorable complexity of hierarchical low-rank matrices and offers, at the same time, a convenient way of prototyping and experimenting with algorithms. A number of applications illustrate the use of the hm-toolbox.

2019

A Dichotomy for Real Weighted Holant Problems

Sangxia Huang

Springer Basel Ag2016