The Γ-algorithm and some applications

In this paper the power of the Γ-algorithm for obtaining the dual of a given cone and some of its multiple applications is discussed. The meaning of each sequential tableau appearing during the process is interpreted. It is shown that each tableau contains the generators of the dual cone of a given cone and that the algorithm updates the dual cone when new generators are incorporated. This algorithm, which is based on the duality concept, allows one to solve many problems in linear algebra, such as determining whether or not a vector belongs to a cone, obtaining the minimal representations of a cone in terms of a linear space and an acute cone, obtaining the intersection of two cones, discussing the compatibility of linear systems of inequalities, solving systems of linear inequalities, etc. The applications are illustrated with examples.     

On-line soft error correction in matrix–matrix multiplication

Soft errors are one-time events that corrupt the state of a computing system but not its overall functionality. Soft errors normally do not interrupt the execution of the affected program, but the affected computation results cannot be trusted any more. A well known technique to correct soft errors in matrix–matrix multiplication is algorithm-based fault tolerance (ABFT). While ABFT achieves much better efficiency than triple modular redundancy (TMR) – a traditional general technique to correct soft errors, both ABFT and TMR detect errors off-line after the computation is finished. This paper extends the traditional ABFT technique from off-line to on-line so that soft errors in matrix–matrix multiplication can be detected in the middle of the computation during the program execution and higher efficiency can be achieved by correcting the corrupted computations in a timely manner. Experimental results demonstrate that the proposed technique can correct one error every ten seconds with negligible (i.e. less than 1%) performance penalty over the ATLAS dgemm().     

A classification of some regular p-groups and its applications

In this paper we classify regular p-groups with type invariants (e, 1,1,1) for e≥2 and (1,1,1,1,1). As a by-product, we give a new approach to the classification of groups of order p5, p ≥ 5 a prime.     

A multiparameter Garsia–Rodemich–Rumsey inequality and some applications

We extend the classical Garsia–Rodemich–Rumsey inequality to the multiparameter situation. The new inequality is applied to obtain some joint Hölder continuity along the rectangles for fractional Brownian fields W(t,x)$W(t,x)$ and for the solution u(t,y)$u(t,y)$ of the stochastic heat equation with additive white noise.     

Localized cohomology and some applications of Popa’s cocycle superrigidity theorem

We prove that orbit equivalence of measure preserving ergodic a.e. free actions of a countable group with the relative property (T) is a complete analytic equivalence relation.     

The Bakry–Emery Ricci tensor and its applications to some compactness theorems

Let (M, g) be a complete and connected Riemannian manifold of dimension n. By using the Bakry–Emery Ricci curvature tensor on M, we prove two theorems which correspond to the Myers compactness theorem.     

A very simple proof of Pascal’s hexagon theorem and some applications

In this article we present a simple and elegant algebraic proof of Pascal’s hexagon theorem which requires only knowledge of basics on conic sections without theory of projective transformations. Also, we provide an efficient algorithm for finding an equation of the conic containing five given points and a criterion for verification whether a set of points is a subset of the conic.     

On the strong Brillinger-mixing property of α-determinantal point processes and some applications

First, we derive a representation formula for all cumulant density functions in terms of the non-negative definite kernel function C(x, y) defining an α-determinantal point process (DPP). Assuming absolute integrability of the function C₀(x) = C(o, x), we show that a stationary α-DPP with kernel function C₀(x) is “strongly” Brillinger-mixing, implying, among others, that its tail-σ-field is trivial. Second, we use this mixing property to prove rates of normal convergence for shot-noise processes and sketch some applications to statistical second-order analysis of α-DPPs.     

Estimates on the solution of a schrödinger equation and some applications

Dedicated to Elliott Lieb on the occasion of his 60th birthday.     

Fast algorithms for floating-point interval matrix multiplication

We discuss several methods for real interval matrix multiplication. First, earlier studies of fast algorithms for interval matrix multiplication are introduced: naive interval arithmetic, interval arithmetic by midpoint-radius form by Oishi-Rump and its fast variant by Ogita-Oishi. Next, three new and fast algorithms are developed. The proposed algorithms require one, two or three matrix products, respectively. The point is that our algorithms quickly predict which terms become dominant radii in interval computations. We propose a hybrid method to predict which algorithm is suitable for optimizing performance and width of the result. Numerical examples are presented to show the efficiency of the proposed algorithms.     

New frameworks for Montgomery's modular multiplication method

We present frameworks for fast modular multiplication based on a modification of Montgomery's original method. For (fixed) large integers, our algorithms may be significantly faster than conventional methods. Our techniques may also be extended to modular polynomial arithmetic.

     

Error‐free transformation of matrix multiplication with a posteriori validation

In this study, we examine the accurate matrix multiplication in floating‐point arithmetic. We demonstrate the error‐free transformations of matrix multiplication using high performance basic linear algebra subprograms. These transformations can be applied to accurately compute the product of two matrices using floating‐point entries. A key technique for this calculation is error‐free splitting in floating‐point matrices. In this study, we improve upon our previous method by a posteriori validation using floating‐point exception. In the method, we utilize the presence of overflow in a positive manner for detecting whether rounding error occurs. If overflow occurs, the result contains some exceptional values such as and NaN , that is, the method fails by necessity. Otherwise, we can confirm that no rounding error occurs in the process. Therefore, reducing the possibility of overflow is important. The numerical results suggest that the proposed algorithm provides more accurate results compared with the original algorithm. Moreover, for the product of n × n matrices, when , the new algorithm reduces the computing time for error‐free transformation by an average of 20 % and up to 30 % compared with the original algorithm. Furthermore, the new algorithm can be used when matrix multiplication is performed using divide‐and‐conquer methods. Copyright © 2016 John Wiley & Sons, Ltd.     

A practical algorithm for faster matrix multiplication

The purpose of this paper is to present an algorithm for matrix multiplication based on a formula discovered by Pan [7]. For matrices of order up to 10 000, the nearly optimum tuning of the algorithm results in a rather clear non‐recursive one‐ or two‐level structure with the operation count comparable to that of the Strassen algorithm [9]. The algorithm takes less workspace and has better numerical stability as compared to the Strassen algorithm, especially in Winograd's modification [2]. Moreover, its clearer and more flexible structure is potentially more suitable for efficient implementation on modern supercomputers. Copyright © 1999 John Wiley & Sons, Ltd.     

Bivariate identities related to Chebyshev and Dickson polynomials over Fq

Let ${\mathbb{F}}_q$ be a field of q elements, where q is a power of an odd prime p. The polynomial $f(y)\in {\mathbb{F}}_q[y]$ defined by$f(y):={(1+\sqrt{y})}^{(q+1)/2}+{(1-\sqrt{y})}^{(q+1)/2}$ has the property that$f(1-y)=\rho (2)f(y),$ where ρ is the quadratic character on ${\mathbb{F}}_q$. This univariate identity was applied to prove a recent theorem of N. Katz. We formulate and prove a bivariate extension, and give an application to quadratic residuacity.     

Counting functions and expected values for the lattice profile at n

Recently, Dorfer and Winterhof introduced and analyzed a lattice test for sequences of length n over a finite field. We determine the number of sequences η of length n with given largest dimension S_n(η)=S for passing this test. From this result we derive an exact formula for the expected value of S_n(η). For the binary case we characterize the (infinite) sequences η with maximal possible S_n(η) for all n.     

Cauchy型矩阵及其逆矩阵的快速三角分解

Abstract, In this paper,algorithms for determining the triangular factorization of Cauchy typematrices and their inverses are derived by using O(n2) operations.     

棋盘游戏与有限域上多项式分解算法

将有限域F_2上多项式分解问题转化为一种对应的棋盘游戏,利用后者的性质设计了一个F_2上m+n-2次多项式f(x)分解为一个m-1次多项式与一个n-1次多项式的判断、分解算法,并对算法的复杂度进行了分析.算法的一个优势是,如果f(x)不能按要求分解,也可以找到一个与f(x)相近(这里指系数相异项较少)的多项式的分解.     

r-对称循环矩阵及逆矩阵三角分解的快速算法

根据r-对称循环矩阵的特殊结构给出了求这类矩阵本身及其逆矩阵三角分解的快速算法,算法的运算量均为O(n2),一般矩阵及逆矩阵三角分解的运算量均为O(n3).     

Fast solution of unsymmetric banded Toeplitz systems by means of spectral factorizations and Woodbury's formula

A fast algorithm for solving systems of linear equations with banded Toeplitz matrices is studied. An important step in the algorithm is a novel method for the spectral factorization of the generating function associated with the Toeplitz matrix. The spectral factorization is extracted from the right deflating subspaces corresponding to the eigenvalues inside and outside the open unit disk of a companion matrix pencil constructed from the coefficients of the generating function. The factorization is followed by the Woodbury inversion formula and solution of several banded triangular systems. Stability of the algorithm is discussed and its performance is demonstrated by numerical experiments. Copyright © 2012 John Wiley & Sons, Ltd.