In this paper, an efficient multiple-precision floating-point fused multiply-add (FMA) unit is proposed. The proposed FMA supports not only single-precision, double-precision, and quadruple-precision ...operations, as some previous works do, but also half-precision operations. The proposed FMA architecture can execute one quadruple-precision operation, or two parallel double-precision operations, or four parallel single-precision operations, or eight parallel half-precision operations every clock cycle. In addition to the support of normal FMA operations, the proposed FMA also supports mixed-precision FMA operations and mixed-precision dot-product operations. Specifically, the products of two lower precision multiplications can be accumulated to a higher precision addend. By setting the operands of one multiplication to zeros, the proposed FMA can also perform mixed-precision FMA operations. Support for mixed-precision FMA and mixed-precision dot-product is newly added but it only consumes 6.5 percent more area compared to a normal multiple-precision FMA unit. Compared to the state-of-the-art multiple-precision FMA design, the proposed FMA supports more floating-point operations such as half-precision FMA operations and mixed-precision operations with only 10.6 percent larger area.
This article presents a multiple-precision binary floating-point library, written in the ISO C language, and based on the GNU MP library. Its particularity is to extend to arbitrary-precision, ideas ...from the IEEE 754 standard, by providing
correct rounding
and
exceptions
. We demonstrate how these strong semantics are achieved---with no significant slowdown with respect to other arbitrary-precision tools---and discuss a few applications where such a library can be useful.
Consider the following two-player communication process to decide a language
L
: The first player holds the entire input
x
but is polynomially bounded; the second player is computationally unbounded ...but does not know any part of
x
; their goal is to decide cooperatively whether
x
belongs to
L
at small cost, where the cost measure is the number of bits of communication from the first player to the second player.
For any integer
d
≥ 3 and positive real
ε
, we show that, if satisfiability for
n
-variable
d
-CNF formulas has a protocol of cost
O
(
nd
−
ε
), then coNP is in NP/poly, which implies that the polynomial-time hierarchy collapses to its third level. The result even holds when the first player is conondeterministic, and is tight as there exists a trivial protocol for
ε
= 0. Under the hypothesis that coNP is not in NP/poly, our result implies tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs.
By reduction, similar results hold for other NP-complete problems. For the vertex cover problem on
n
-vertex
d
-uniform hypergraphs, this statement holds for any integer
d
≥ 2. The case
d
= 2 implies that no NP-hard vertex deletion problem based on a graph property that is inherited by subgraphs can have kernels consisting of
O
(
k
2 −
ε
) edges unless coNP is in NP/poly, where
k
denotes the size of the deletion set. Kernels consisting of
O
(
k
2) edges are known for several problems in the class, including vertex cover, feedback vertex set, and bounded-degree deletion.
Particle swarm optimization (PSO) is predominately used to find solutions for continuous optimization problems. As the operators of PSO are originally designed in an n -dimensional continuous space, ...the advancement of using PSO to find solutions in a discrete space is at a slow pace. In this paper, a novel set-based PSO (S-PSO) method for the solutions of some combinatorial optimization problems (COPs) in discrete space is presented. The proposed S-PSO features the following characteristics. First, it is based on using a set-based representation scheme that enables S-PSO to characterize the discrete search space of COPs. Second, the candidate solution and velocity are defined as a crisp set, and a set with possibilities, respectively. All arithmetic operators in the velocity and position updating rules used in the original PSO are replaced by the operators and procedures defined on crisp sets, and sets with possibilities in S-PSO. The S-PSO method can thus follow a similar structure to the original PSO for searching in a discrete space. Based on the proposed S-PSO method, most of the existing PSO variants, such as the global version PSO, the local version PSO with different topologies, and the comprehensive learning PSO (CLPSO), can be extended to their corresponding discrete versions. These discrete PSO versions based on S-PSO are tested on two famous COPs: the traveling salesman problem and the multidimensional knapsack problem. Experimental results show that the discrete version of the CLPSO algorithm based on S-PSO is promising.
Having developed multiobjective optimization algorithms using evolutionary optimization methods and demonstrated their niche on various practical problems involving mostly two and three objectives, ...there is now a growing need for developing evolutionary multiobjective optimization (EMO) algorithms for handling many-objective (having four or more objectives) optimization problems. In this paper, we recognize a few recent efforts and discuss a number of viable directions for developing a potential EMO algorithm for solving many-objective optimization problems. Thereafter, we suggest a reference-point-based many-objective evolutionary algorithm following NSGA-II framework (we call it NSGA-III) that emphasizes population members that are nondominated, yet close to a set of supplied reference points. The proposed NSGA-III is applied to a number of many-objective test problems with three to 15 objectives and compared with two versions of a recently suggested EMO algorithm (MOEA/D). While each of the two MOEA/D methods works well on different classes of problems, the proposed NSGA-III is found to produce satisfactory results on all problems considered in this paper. This paper presents results on unconstrained problems, and the sequel paper considers constrained and other specialties in handling many-objective optimization problems.
We show that any explicit example for a tensor
A
:
n
r
→
F
with tensor-rank ≥
n
rċ(1−o(1))
, where
r
=
r
(
n
) ≤ log
n
/log log
n
is super-constant, implies an explicit super-polynomial lower bound ...for the size of general arithmetic formulas over F. This shows that strong enough lower bounds for the size of arithmetic formulas of depth 3 imply super-polynomial lower bounds for the size of general arithmetic formulas.
One component of our proof is a new approach for homogenization and multilinearization of arithmetic formulas, that gives the following results:
We show that for any
n
-variate homogeneous polynomial
f
of degree
r
, if there exists a (fanin-2) formula of size
s
and depth
d
for
f
then there exists a homogeneous formula of size
O
((
d
+
r
+1 r) ċ
s
) for
f
. In particular, for any
r
≤
O
(log
n
), if there exists a polynomial size formula for
f
then there exists a polynomial size homogeneous formula for
f
. This refutes a conjecture of Nisan and Wigderson 1996 and shows that super-polynomial lower bounds for homogeneous formulas for polynomials of small degree imply super-polynomial lower bounds for general formulas.
We show that for any
n
-variate set-multilinear polynomial
f
of degree
r
, if there exists a (fanin-2) formula of size
s
and depth
d
for
f
, then there exists a set-multilinear formula of size
O
((
d
+ 2)
r
ċ
s
) for
f
. In particular, for any
r
≤
O
(log
n
/log log
n
), if there exists a polynomial size formula for
f
then there exists a polynomial size set-multilinear formula for
f
. This shows that super-polynomial lower bounds for set-multilinear formulas for polynomials of small degree imply super-polynomial lower bounds for general formulas.
Enumeration of a dot array is faster and easier if the items form recognizable subgroups. This phenomenon, which has been termed “groupitizing,” appears in children after one year of formal education ...and correlates with arithmetic abilities. We formulated and tested the hypothesis that groupitizing reflects an ability to sidestep counting by using arithmetic shortcuts, for instance, using the grouping structure to add or multiply rather than just count. Three groups of students with different levels of familiarity with mathematics were asked to name the numerosity of sets of 1–15 dots in various arrangements, for instance, 9 represented as a single group of 9 items, three distinct groups of 2, 3, and 4 items (affording addition 2 + 3 + 4), or three identical groups of 3 items (affording multiplication 3 × 3). Grouping systematically improved enumeration performance, regardless of whether the items were grouped spatially or by color alone, but only when an array was divided into subgroups with the same number of items. Response times and error patterns supported the hypothesis of a multiplication process. Our results demonstrate that even a simple enumeration task involves mental arithmetic.
Fast Feature Pyramids for Object Detection Dollar, Piotr; Appel, Ron; Belongie, Serge ...
IEEE transactions on pattern analysis and machine intelligence,
08/2014, Letnik:
36, Številka:
8
Journal Article
Recenzirano
Odprti dostop
Multi-resolution image features may be approximated via extrapolation from nearby scales, rather than being computed explicitly. This fundamental insight allows us to design object detection ...algorithms that are as accurate, and considerably faster, than the state-of-the-art. The computational bottleneck of many modern detectors is the computation of features at every scale of a finely-sampled image pyramid. Our key insight is that one may compute finely sampled feature pyramids at a fraction of the cost, without sacrificing performance: for a broad family of features we find that features computed at octave-spaced scale intervals are sufficient to approximate features on a finely-sampled pyramid. Extrapolation is inexpensive as compared to direct feature computation. As a result, our approximation yields considerable speedups with negligible loss in detection accuracy. We modify three diverse visual recognition systems to use fast feature pyramids and show results on both pedestrian detection (measured on the Caltech, INRIA, TUD-Brussels and ETH data sets) and general object detection (measured on the PASCAL VOC). The approach is general and is widely applicable to vision algorithms requiring fine-grained multi-scale analysis. Our approximation is valid for images with broad spectra (most natural images) and fails for images with narrow band-pass spectra (e.g., periodic textures).
An arithmetic formula is multilinear if the polynomial computed by each of its subformulas is multilinear. We prove that any multilinear arithmetic formula for the permanent or the determinant of an
...n
×
n
matrix is of size super-polynomial in
n
. Previously, super-polynomial lower bounds were not known (for any explicit function) even for the special case of multilinear formulas of constant depth.
This article presents an axiom system for an arithmetic of the even and the odd, one that is stronger than those discussed in Pambuccian (2016) and Menn & Pambuccian (2016). It consists of universal ...sentences in a language extending the usual one with 0, 1, +, ·, <, – with the integer part of the half function \({ \cdot \over 2}\), and two unary operation symbols.
PDF
