A computational comparison of the first nine members of a determinantal family of root-finding methods

For each natural number m greater than one, and each natural number k less than or equal to m, there exists a root-finding iteration function, B_m^(k) defined as the ratio of two determinants that depend on the first m−k derivatives of the given function. This infinite family is derived in Kalantari (J. Comput. Appl. Math. 126 (2000) 287–318) and its order of convergence is analyzed in Kalantari (BIT 39 (1999) 96–109). In this paper we give a computational study of the first nine root-finding methods. These include Newton, secant, and Halley methods. Our computational results with polynomials of degree up to 30 reveal that for small degree polynomials B_m^(k−1) is more efficient than B_m^(k), but as the degree increases, B_m^(k) becomes more efficient than B_m^(k−1). The most efficient of the nine methods is B₄⁽⁴⁾, having theoretical order of convergence equal to 1.927. Newton's method which is often viewed as the method of choice is in fact the least efficient method.     

On the weighted enumeration of alternating sign matrices and descending plane partitions

We prove a conjecture of Mills, Robbins and Rumsey [Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (3) (1983) 340-359] that, for any n, k, m and p, the number of n×n alternating sign matrices (ASMs) for which the 1 of the first row is in column k+1 and there are exactly m −1?s and m+p inversions is equal to the number of descending plane partitions (DPPs) for which each part is at most n and there are exactly k parts equal to n, m special parts and p nonspecial parts. The proof involves expressing the associated generating functions for ASMs and DPPs with fixed n as determinants of n×n matrices, and using elementary transformations to show that these determinants are equal. The determinants themselves are obtained by standard methods: for ASMs this involves using the Izergin-Korepin formula for the partition function of the six-vertex model with domain-wall boundary conditions, together with a bijection between ASMs and configurations of this model, and for DPPs it involves using the Lindström-Gessel-Viennot theorem, together with a bijection between DPPs and certain sets of nonintersecting lattice paths.     

New formulas for approximation of π and other transcendental numbers

We derive many new formulas for the approximation of π. The formulas make use of a sequence of iteration functions called the basic family; a nontrivial determinantal generalization of Taylor's theorem; other ingredients; as well as several new results presented in the present paper. In one scheme, one evaluates members of the basic family, for an appropriately selected function, all at the same input. This scheme generates almost a fixed and preselected number of digits in each successive evaluation. The computation amounts to the evaluation of a homogeneous linear recursive formula and is equivalent to the computation of special Toeplitz matrix determinants. The approximations of π obtained via this scheme are within simple algebraic extensions of the rational field. In a second scheme, the fixed-point iteration is applied to any fixed member of the basic family, while selecting an appropriate function. In this scheme for each natural number we prove convergence of order m, starting from the initial point. We report on some preliminary computational results obtained via Maple. Analogous formulas can be used to approximate other transcendental numbers. For instance, we also give a formula for the approximation of e. In fact, our results give new formulas and arbitrary high-order methods for the approximation of roots of certain analytic functions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Determinants of the Hypergeometric Period Matrices of an Arrangement and Its Dual

We fix three natural numbers k, n, N, such that n+k+1 = N, and introduce the notion of two dual arrangements of hyperplanes. One of the arrangements is an arrangement of N hyperplanes in a k-dimensional affine space, the other is an arrangement of N hyperplanes in an n-dimensional affine space. We assign weights α ₁, . . . , α _N to the hyperplanes of the arrangements and for each of the arrangements consider the associated period matrices. The first is a matrix of k-dimensional hypergeometric integrals and the second is a matrix of n-dimensional hypergeometric integrals. The size of each matrix is equal to the number of bounded domains of the corresponding arrangement. We show that the dual arrangements have the same number of bounded domains and the product of the determinants of the period matrices is equal to an alternating product of certain values of Euler’s gamma function multiplied by a product of exponentials of the weights. Supported in part by NSF grant DMS-0244579.     

Convergence of the Multigrid Method of Ill-conditioned Block Toeplitz Systems

We study the solutions of block Toeplitz systems A _mn u = b by the multigrid method (MGM). Here the block Toeplitz matrices A _mn are generated by a nonnegative function f (x,y) with zeros. Since the matrices A _mn are ill-conditioned, the convergence factor of classical iterative methods will approach 1 as the size of the matrices becomes large. These classical methods, therefore, are not applicable for solving ill-conditioned systems. The MGM is then proposed in this paper. For a class of block Toeplitz matrices, we show that the convergence factor of the two-grid method (TGM) is uniformly bounded below 1 independent of mn and the full MGM has convergence factor depending only on the number of levels. The cost per iteration for the MGM is of O(mn log mn) operations. Numerical results are given to explain the convergence rate.     

Density Estimation on the Stiefel Manifold

This paper develops the theory of density estimation on the Stiefel manifoldV_{k, m}, whereV_{k, m}is represented by the set ofm×kmatricesXsuch thatX′X=I_k, thek×kidentity matrix. The density estimation by the method of kernels is considered, proposing two classes of kernel density estimators with small smoothing parameter matrices and for kernel functions of matrix argument. Asymptotic behavior of various statistical measures of the kernel density estimators is investigated for small smoothing parameter matrix and/or for large sample size. Some decompositions of the Stiefel manifoldV_{k, m}play useful roles in the investigation, and the general discussion is applied and examined for a special kernel function. Alternative methods of density estimation are suggested, using decompositions ofV_{k, m}.     

Subtotally positive and Monge matrices

A real matrix is called k-subtotally positive if the determinants of all its submatrices of order at most k are positive. We show that for an m × n matrix, only mn inequalities determine such class for every k, 1 ? k ? min(m,n). Spectral properties of square k-subtotally positive matrices are studied. Finally, completion problems for 2-subtotally positive matrices and their additive counterpart, the anti-Monge matrices, are investigated. Since totally positive matrices are 2-subtotally positive as well, the presented necessary conditions for this completion problem are also necessary conditions for totally positive matrices.     

Ramsey functions involving with large

For fixed integers m,k2, it is shown that the k-color Ramsey number r_k(K_m,n) and the bipartite Ramsey number b_k(m,n) are both asymptotically equal to k^mn as n→∞, and that for any graph H on m vertices, the two-color Ramsey number is at most (1+o(1))n^m+1/(logn)^m-1. Moreover, the order of magnitude of is proved to be n^m+1/(logn)^m if H≠K_m as n→∞.     

Subgraphs of large connectivity and chromatic number in graphs of large chromatic number

For each pair k, m of natural numbers there exists a natural number f(k, m) such that every f(k, m)-chromatic graph contains a k-connected subgraph of chromatic number at least m.     

Isomorphy classes of finite order automorphisms of SL(2,k)

In this paper, we consider the order m k-automorphisms of SL(2,k). We first characterize the forms that order m k-automorphisms of SL(2,k) take and then we find simple conditions on matrices A and B, involving eigenvalues and the field that the entries of A and B lie in, that are equivalent to isomorphy between the order m k-automorphisms Inn_A and Inn_B. We examine the number of isomorphy classes and conclude with examples for selected fields.     

Possible numbers of positive entries of imprimitive nonnegative matrices

Zhan, X., Extremal numbers of positive entries of imprimitive nonnegative matrix, Linear Algebra Appl. (in press) has determined the maximum and minimum numbers of positive entries of imprimitive irreducible nonnegative matrices with a given imprimitivity index. Let σ( A ) denote the number of positive entries of a matrix A. Let M(n,?k) and m(n,?k) denote the maximum and minimum numbers of positive entries of imprimitive irreducible nonnegative matrices of order n with a given imprimitivity index k, respectively. In this article, we prove that for any positive integer d with m(n,k)≤ d?≤?M(n,k), there exists an n?×?n irreducible nonnegative matrix A with imprimitivity index k such that?σ?(A)=d.     

Multi-latin squares

A multi-latin square of order n and index k is an n×n array of multisets, each of cardinality k, such that each symbol from a fixed set of size n occurs k times in each row and k times in each column. A multi-latin square of index k is also referred to as a k-latin square. A 1-latin square is equivalent to a latin square, so a multi-latin square can be thought of as a generalization of a latin square.In this note we show that any partially filled-in k-latin square of order m embeds in a k-latin square of order n, for each n≥2m, thus generalizing Evans’ Theorem. Exploiting this result, we show that there exist non-separable k-latin squares of order n for each n≥k+2. We also show that for each n≥1, there exists some finite value g(n) such that for all k≥g(n), every k-latin square of order n is separable.We discuss the connection between k-latin squares and related combinatorial objects such as orthogonal arrays, latin parallelepipeds, semi-latin squares and k-latin trades. We also enumerate and classify k-latin squares of small orders.     

A generalization of Müller’s iteration method based on standard information

For finding a root of a function f, Müler’s method is a root-finding algorithm using three values of f in every step. The natural values available are values of f and values of its first number of derivatives, called standard information. Based on standard information, we construct an iteration method with maximal order of convergence. It is a natural generalization of Müller’s iteration method. This work was partially supported by National Natural Science Foundation of China (Grant No. 10471128), NSFC (Grant No. 10731060).     

Determinantal varieties over truncated polynomial rings

We study components and dimensions of higher-order determinantal varieties obtained by considering generic m×n (m?n) matrices over rings of the form F[t]/(t^k), and for some fixed r, setting the coefficients of powers of t of all r×r minors to zero. These varieties can be interpreted as spaces of (k−1)th order jets over the classical determinantal varieties; a special case of these varieties first appeared in a problem in commuting matrices. We show that when r=m, the varieties are irreducible, but when r<m, these varieties are reducible. We show that when r=2<m (any k), there are exactly ⌊k/2⌋+1 components, which we determine explicitly, and for general r<m, we show there are at least ⌊k/2⌋+1 components. We also determine the components explicitly for k=2 and 3 for all values of r (for k=3 for all but finitely many pairs of (m,n)).     

Coloring of distance graphs with intervals as distance sets

Let D be a set of positive integers. The distance graph G(Z,D) with distance set D is the graph with vertex set Z in which two vertices x,y are adjacent if and only if |x−y|D. The fractional chromatic number, the chromatic number, and the circular chromatic number of G(Z,D) for various D have been extensively studied recently. In this paper, we investigate the fractional chromatic number, the chromatic number, and the circular chromatic number of the distance graphs with the distance sets of the form D_m,[k,k^′]={1,2,…,m}−{k,k+1,…,k^′}, where m, k, and k^′ are natural numbers with m≥k^′≥k. In particular, we completely determine the chromatic number of G(Z,D_m,[2,k^′]) for arbitrary m, and k^′.     

A collocation method for differential equations with one‐point Taylor initial conditions

This paper presents a new multistep collocation method for nth order differential equations. The interval of interest is first divided into N subintervals. By determining interval conditions in Taylor interpolation in each subinterval, Taylor polynomials are calculated with different step lengths. Then the obtained solutions in each subinterval are used as initial conditions in the next step. Optimal error is assessed using Peano lemma, which shows that the errors decay by decreasing the step length. In particular, for fixed step length h, the error is of O(m^?m), where m is the number of collocation points in each subinterval. Meanwhile, for fixed m, the error is of O(h^m). Numerical examples demonstrate the validity and high accuracy of the proposed method even for stiff problems.     

Refined enumerations of alternating sign matrices: monotone (<Emphasis Type="Italic">d</Emphasis>,<Emphasis Type="Italic">m</Emphasis>)-trapezoids with prescribed top and bottom row

Monotone triangles are plane integer arrays of triangular shape with certain monotonicity conditions along rows and diagonals. Their significance is mainly due to the fact that they correspond to n×n alternating sign matrices when prescribing (1,2,…,n) as bottom row of the array. We define monotone (d,m)-trapezoids as monotone triangles with m rows where the d−1 top rows are removed. (These objects are also equivalent to certain partial alternating sign matrices.) It is known that the number of monotone triangles with bottom row (k ₁,…,k _n ) is given by a polynomial α(n;k ₁,…,k _n ) in the k _i ’s. The main purpose of this paper is to show that the number of monotone (d,m)-trapezoids with prescribed top and bottom row appears as a coefficient in the expansion of a specialisation of α(n;k ₁,…,k _n ) with respect to a certain polynomial basis. This settles a generalisation of a recent conjecture of Romik et al. (Adv. Math. 222:2004–2035, 2009). Among other things, the result is used to express the number of monotone triangles with bottom row (1,2,…,i−1,i+1,…,j−1,j+1,…,n) (which is, by the standard bijection, also the number of n×n alternating sign matrices with given top two rows) in terms of the number of n×n alternating sign matrices with prescribed top and bottom row, and, by a formula of Stroganov for the latter numbers, to provide an explicit formula for the first numbers. (A formula of this type was first derived by Karklinsky and Romik using the relation of alternating sign matrices to the six-vertex model.)     

Convergence of the iteration of Halley’s family and Smale operator class in Banach space

Smale operator classes of any order for nonlinear operators in Banach space are introduced. For an operatorf in Smale operator class of orderk, a proper condition for the convergence and the exact estimations error for the iteration of Halley’s family {H _j,k ⁿ } _n=0 ^∞ (1≤j≤k) are given. This Halley’s family is a higher order explicit generalization of Newton iteration. Project supported by China State Major Key Project for Basic Research and Zhejiang Provincial Natrural Science Foundation.     

Concentrated matrix Langevin distributions

This paper concerns the matrix Langevin distributions, exponential-type distributions defined on the two manifolds of our interest, the Stiefel manifold V_k,m and the manifold P_k,m−k of m×m orthogonal projection matrices idempotent of rank k which is equivalent to the Grassmann manifold G_k,m−k. Asymptotic theorems are derived when the concentration parameters of the distributions are large. We investigate the asymptotic behavior of distributions of some (matrix) statistics constructed based on the sample mean matrices in connection with testing hypotheses of the orientation parameters, and obtain asymptotic results in the estimation of large concentration parameters and in the classification of the matrix Langevin distributions.     

A basic family of iteration functions for polynomial root finding and its characterizations

Let p(x) be a polynomial of degree n?2 with coefficients in a subfield K of the complex numbers. For each natural number m?2, let L_m(x) be the m×m lower triangular matrix whose diagonal entries are p(x) and for each j=1,…,m−1, its jth subdiagonal entries are . For i=1,2, let L_m^i)(x) be the matrix obtained from L_m(x) by deleting its first i rows and its last i columns. L₁⁽¹⁾(x)≡1. Then, the function B_m(x)=x−p(x) defines a fixed-point iteration function having mth order convergence rate for simple roots of p(x). For m=2 and 3, B_m(x) coincides with Newton's and Halley's, respectively. The function B_m(x) is a member of S(m,m+n−2), where for any M?m, S(m,M) is the set of all rational iteration functions g(x) ∈ K(x) such that for all roots θ of p(x), then g(x)=θ+∑_i=m^Mγ_i(x)(θ−x)ⁱ, with γ_i(x) ∈ K(x) and well-defined at any simple root θ. Given g ∈ S(m,M), and a simple root θ of p(x), gⁱ(θ)=0, i=1, …, m−1 and the asymptotic constant of convergence of the corresponding fixed-point iteration is . For B_m(x) we obtain . If all roots of p(x) are simple, B_m(x) is the unique member of S(m,m + n − 2). By making use of the identity , we arrive at two recursive formulas for constructing iteration functions within the S(m,M) family. In particular, the family of B_m(x) can be generated using one of these formulas. Moreover, the other formula gives a simple scheme for constructing a family of iteration functions credited to Euler as well as Schröder, whose mth order member belongs to S(m,mn), m>2. The iteration functions within S(m,M) can be extended to any arbitrary smooth function f, with the uniform replacement of p^(j) with f^(j) in g as well as in γ_m(θ).