Aurifeuillian factorizations and the period of the Bell numbers modulo a prime

We show that the minimum period modulo of the Bell exponential integers is for all primes and several larger . Our proof of this result requires the prime factorization of these periods. For some primes the factoring is aided by an algebraic formula called an Aurifeuillian factorization. We explain how the coefficients of the factors in these formulas may be computed.

     

Set-functions and factorization

Both authors were supported by grants from the National Science Foundation     

Modern factorization methods

In this expository paper the progress in factorization of large integers since the introduction of computers is reported. Thanks to theoretical advances and refinements, as well as to more powerful computers, the practical limit of integers possible to factor has been raised considerably during the past 20 years. The present practical limit is around 10⁷⁵ if supercomputers are used and if much computer time is available.     

Finite factorization domains

An integral domain is a finite factorization domain if each nonzero element of has only finitely many divisors, up to associates. We show that a Noetherian domain is an FFD for each overring of that is a finitely generated -module, is finite. For local this is also equivalent to each being finite. We show that a one-dimensional local domain is an FFD either is finite or is a DVR.

     

Multidimensional butterfly factorization

This paper introduces the multidimensional butterfly factorization as a data-sparse representation of multidimensional kernel matrices that satisfy the complementary low-rank property. This factorization approximates such a kernel matrix of size $N\times N$ with a product of $O(\log ?N)$ sparse matrices, each of which contains $O(N)$ nonzero entries. We also propose efficient algorithms for constructing this factorization when either (i) a fast algorithm for applying the kernel matrix and its adjoint is available or (ii) every entry of the kernel matrix can be evaluated in $O(1)$ operations. For the kernel matrices of multidimensional Fourier integral operators, for which the complementary low-rank property is not satisfied due to a singularity at the origin, we extend this factorization by combining it with either a polar coordinate transformation or a multiscale decomposition of the integration domain to overcome the singularity. Numerical results are provided to demonstrate the efficiency of the proposed algorithms.     

Square form factorization

We present a detailed analysis of SQUFOF, Daniel Shanks' Square Form Factorization algorithm. We give the average time and space requirements for SQUFOF. We analyze the effect of multipliers, either used for a single factorization or when racing the algorithm in parallel.

     

Holomorphic factorization of polynomials

We give necessary and sufficient conditions for a holomorphic factorization of an irreducible polynomial P(s, λ), s ∈ Cⁿ, λ ∈ C, in a domain Ω ? Cⁿ which is connected with the ordering of the real part of the roots of the equation P(s, λ) = 0, s ∈ Ω.     

Idempotent factorization of matrices

Necessary and sufficient conditions are presented for a square matrix over an arbitrary field to be a product of k ≥ 1 idempotent matrices of prescribed nullities.     

Almost-regular factorization of graphs

For integers a and b, 0 ? a ? a ? b, an [a, b]-graph G satisties a ? deg(x, G) ? b for every vertex x of G, and an [a, b]-factor is a spanning subgraph F such that a ? deg(x, F) ? b for every vertex x of F. An [a, b]-factor is almost-regular if b = a + 1. A graph is [a, b]-factorable if its edges can be decomposed into [a, b]-factors. When both K and t are positive integers and s is a nonnegative integer, we prove that every [(12K + 2)t + 2ks, (12k + 4)t + 2ks]-graph is [2k,2k + 1]-factorable. As its corollary, we prove that every [r.r + 1]-graph with r ? 12k² + 2k is [2k + 1]-factorable, which is a partial extension of the two results, one by Thomassen and the other by Era.     

On theLU factorization ofM-matrices

Summary In this paper, we give in Theorem 1 a characterization, based on graph theory, of when anM-matrixA admits anLU factorization intoM-matrices, whereL is a nonsingular lower triangularM-matrix andU is an upper triangularM-matrix. This result generalizes earlier factorization results of Fiedler and Pták (1962) and Kuo (1977). As a consequence of Theorem 1, we show in Theorem 3 that the conditionx ^T A0 ^T for somex>0, for anM-matrixA, is both necessary and sufficient forPAP ^T to admit such anLU factorization for everyn×n permutation matrixP. This latter result extends recent work of Funderlic and Plemmons (1981). Finally, Theorem 1 is extended in Theorem 5 to give a characterization, similarly based on graph theory, of when anM-matrixA admits anLU factorization intoM-matrices.Dedicated to Professor Ky Fan on his sixty-seventh birthday, September 19, 1981.Research supported in part by the Air Force Office of Scientific Research, and by the Department of Energy     

Angular factorization of matrices

Let Q denote a selfadjoint matrix (or operator of finite rank). The factorization of I + Q into the form $\text{I + Q = (I ? W) D(I ? W}{}^1\text{)}$ is considered. The well-known case where W is constrained to be lower triangular while D is diagonal is extended to quadrangular and other generalized-canonical forms. The case where Q is not selfadjoint is also developed. Applications for these results may be found in the realm of multivariate-stochastic approximation, and signal extraction.     

Modified block-approximate factorization strategies

Summary Two variants of modified incomplete block-matrix factorization with additive correction are proposed for the iterative solution of large linear systems of equations. Both rigorous theoretical support and numerical evidence are given displaying their efficiency when applied to discrete second order partial differential equations (PDEs), even in the case of quasi-singular problems.Research supported by the A.B.O.S. (A.G.C.D.) under project 11, within the co-operation between Belgium and Zaire     

Nilpotent factorization of matrices

We show that, with the exception of 2 × 2 nonzero nilpotent matrices, every singular square matrix over an arbitrary field is a product of two nilpotent matrices.     

Sparse bivariate polynomial factorization

Motivated by Sasaki’s work on the extended Hensel construction for solving multivariate algebraic equations, we present a generalized Hensel lifting, which takes advantage of sparsity, for factoring bivariate polynomial over the rational number field. Another feature of the factorization algorithm presented in this article is a new recombination method, which can solve the extraneous factor problem before lifting based on numerical linear algebra. Both theoretical analysis and experimental data show that the algorithm is efficient, especially for sparse bivariate polynomials.     

Synthetic division and matrix factorization

Synthetic division is viewed as a change of basis for polynomials written under the Newton form. Then, the transition matrices obtained from a sequence of changes of basis are used to factorize the inverse of a bidiagonal matrix or a block bidiagonal matrix.     

Dynamic factorization in large-scale optimization

Factorization of linear programming (LP) models enables a large portion of the LP tableau to be represented implicitly and generated from the remaining explicit part. Dynamic factorization admits algebraic elements which change in dimension during the course of solution. A unifying mathematical framework for dynamic row factorization is presented with three algorithms which derive from different LP model row structures: generalized upper bound rows, pure network rows, and generalized network rows. Each of these structures is a generalization of its predecessors, and each corresponding algorithm exhibits just enough additional richness to accommodate the structure at hand within the unified framework. Implementation and computational results are presented for a variety of real-world models. These results suggest that each of these algorithms is superior to the traditional, non-factorized approach, with the degree of improvement depending upon the size and quality of the row factorization identified.Corresponding author.     

Spectral factorization of Laurent polynomials

We analyse the performance of five numerical methods for factoring a Laurent polynomial, which is positive on the unit circle, as the modulus squared of a real algebraic polynomial. It is found that there is a wide disparity between the methods, and all but one of the methods are significantly influenced by the variation in magnitude of the coefficients of the Laurent polynomial, by the closeness of the zeros of this polynomial to the unit circle, and by the spacing of these zeros. This revised version was published online in August 2006 with corrections to the Cover Date.