Full-rank block LDL ? decomposition and the inverses of n×n block matrices

Full-rank block LDL ^? decomposition of a Hermitian n×n block matrix A is examined, where the iterative procedure evaluating the sub-matrices appearing in L and D is provided. This factorization is used to evaluate the inverse and Moore-Penrose inverse of a Hermitian n×n block matrix. The method for the calculation of the Moore-Penrose inverse of an arbitrary 2×2 block matrix is also provided. Therefore, matrix products A ^? A and AA ^? and the corresponding full-rank block LDL ^? factorizations are observed. Also, a simple explicit formulae calculating the solution vector components of the normal system of equations is stated, where the LDL ^? decomposition of the system matrix is done.     

Reorthogonalized block classical Gram–Schmidt

A reorthogonalized block classical Gram–Schmidt algorithm is proposed that factors a full column rank matrix $A$ into $A=QR$ where $Q$ is left orthogonal (has orthonormal columns) and $R$ is upper triangular and nonsingular. This block Gram–Schmidt algorithm can be implemented using matrix–matrix operations making it more efficient on modern architectures than orthogonal factorization algorithms based upon matrix-vector operations and purely vector operations. Gram–Schmidt orthogonal factorizations are important in the stable implementation of Krylov space methods such as GMRES and in approaches to modifying orthogonal factorizations when columns and rows are added or deleted from a matrix. With appropriate assumptions about the diagonal blocks of $R$ , the algorithm, when implemented in floating point arithmetic with machine unit $\varepsilon _M$ , produces $Q$ and $R$ such that $\Vert I- Q ^T\!~ Q \Vert =O(\varepsilon _M)$ and $\Vert A-QR \Vert =O(\varepsilon _M\Vert A \Vert )$ . The first of these bounds has not been shown for a block Gram–Schmidt procedure before. As consequence of these results, we provide a different analysis, with a slightly different assumption, that re-establishes a bound of Giraud et al. (Num Math, 101(1):87–100, 2005) for the CGS2 algorithm.     

Schur’s theorem for a block Hadamard product

We define a generalized Kronecker product for block matrices, mention some of its properties, and apply it to the study of a block Hadamard product of positive semidefinite matrices, which was defined by Horn, Mathias, and Nakamura. Under strong commutation assumptions we obtain generalizations of Schur’s theorem and of Oppenheim’s inequality.     

Modified block iterative algorithm for Quasi-?-asymptotically nonexpansive mappings and equilibrium problem in banach spaces

The purpose of this paper is to propose a modified block iterative algorithm for find a common element of the set of common fixed points of an infinite family of quasi-?-asymptotically nonexpansive mappings and the set of an equilibrium problem. Under suitable conditions, some strong convergence theorems are established in a uniformly smooth and strictly convex Banach space with the Kadec-Klee property. As an application, at the end of the paper a numerical example is given. The results presented in the paper improve and extend the corresponding results in Qin et al. [Convergence theorems of common elements for equilibrium problems and fixed point problem in Banach spaces, J. Comput. Appl. Math., 225, 2009, 20-30], Zhou et al. [Convergence theorems of a modified hybrid algorithm for a family of quasi-?-asymptotically nonexpansive mappings, J. Appl. Math. Compt., 17 March, 2009, doi:10.1007/s12190-009-0263-4], Takahashi and Zembayshi [Strong and weak convergence theorems for equilibrium problems and relatively nonexpansive mappings in Banach spaces, Nonlinear Anal., 70, 2009, 45-57], Wattanawitoon and Kumam [Strong convergence theorems by a new hybrid projection algorithm for fixed point problem and equilibrium problems of two relatively quasi-nonexpansive mappings, Nonlinear Anal. Hybrid Syst., 3, 2009, 11-20] and Matsushita and Takahashi [A strong convergence theorem for relatively nonexpansive mappings in Banach spaces, J. Approx. Theory, 134, 2005, 257-266] and others.     

The Moore–Penrose inverse of block magic rectangles

As is known, a semi-magic square is an n?×?n matrix having the sum of entries in each row and each column equal to a constant. This note generalizes this notion and introduce a special class of block matrices called block magic rectangles. It is proved that the Moore–Penrose inverse of a block magic rectangle is also a block magic rectangle.     

On the longest block in Lüroth expansion

In this paper, for a finite subset $A?\{2,3,?\}$, we introduce the notion of longest block function $L_n(x,A)$ for the Lüroth expansion of $x\in [0,1)$ with respect to A and consider the asymptotic behavior of $L_n(x,A)$ as n tends to ∞. We also obtain the Hausdorff dimensions of the level sets and exceptional set arising from the longest block function.     

Directed packings with block size 5 and even ν

Let andk be positive integers. A transitively orderedk-tuple (a ₁,a ₂,...,a _k) is defined to be the set {(a _i, a_j) 1i<jk} consisting ofk(k–1)/2 ordered pairs. A directed packing with parameters ,k and index =1, denoted byDP(k, 1; ), is a pair (X, A) whereX is a -set (of points) andA is a collection of transitively orderedk-tuples ofX (called blocks) such that every ordered pair of distinct points ofX occurs in at most one block ofA. The greatest number of blocks required in aDP(k, 1; ) is called packing number and denoted byDD(k, 1; ). It is shown in this paper that for all even integers , where [x] is the floor ofx.     

A flexible block classical Gram–Schmidt skeleton with reorthogonalization

We investigate a variant of the reorthogonalized block classical Gram–Schmidt method for computing the QR factorization of a full column rank matrix. Our aim is to bound the loss of orthogonality even when the first local QR algorithm is only conditionally stable. In particular, this allows the use of modified Gram–Schmidt instead of Householder transformations as the first local QR algorithm. Numerical experiments confirm the stable behavior of the new variant. We also examine the use of non-QR local factorization and show by example that the resulting variants, although less stable, may also be applied to ill-conditioned problems.     

On the extreme eigenvalues of block 2 × 2 Hermitian matrices

The lower bound

Group inverses for some 2 × 2 block matrices over rings

We first consider the group inverses of the block matrices (A0BC) over a weakly finite ring. Then we study the sufficient and necessary conditions for the existence and the representations of the group inverses of the block matrices (ACBD) over a ring with unity 1 under the following conditions respectively: (i) B = C, D = 0, B^# and (B^πA) ^# both exist; (ii) B is invertible and m = n; (iii) A^# and (D - CA^#B)^# both exist, C = CAA^# , where A and D are m × m and n × n matrices, respectively.     

A parallel interior point decomposition algorithm for block angular semidefinite programs

We present a two phase interior point decomposition framework for solving semidefinite (SDP) relaxations of sparse maxcut, stable set, and box constrained quadratic programs. In phase 1, we suitably modify the matrix completion scheme of Fukuda et al. (SIAM J. Optim. 11:647–674, 2000) to preprocess an existing SDP into an equivalent SDP in the block-angular form. In phase 2, we solve the resulting block-angular SDP using a regularized interior point decomposition algorithm, in an iterative fashion between a master problem (a quadratic program); and decomposed and distributed subproblems (smaller SDPs) in a parallel and distributed high performance computing environment. We compare our MPI (Message Passing Interface) implementation of the decomposition algorithm on the distributed Henry2 cluster with the OpenMP version of CSDP (Borchers and Young in Comput. Optim. Appl. 37:355–369, 2007) on the IBM Power5 shared memory system at NC State University. Our computational results indicate that the decomposition algorithm (a) solves large SDPs to 2–3 digits of accuracy where CSDP runs out of memory; (b) returns competitive solution times with the OpenMP version of CSDP, and (c) attains a good parallel scalability. Comparing our results with Fujisawa et al. (Optim. Methods Softw. 21:17–39, 2006), we also show that a suitable modification of the matrix completion scheme can be used in the solution of larger SDPs than was previously possible.     

Orthogonal geometries over finite fields with characteristic ≠2 and block designs

By taking as blocks certain subspace-pairs of an orthogonal geometry over a finite field with characteristic 2 we construct some new types of BIB designs and PBIB designs whose parameters are also given.     

On the E- and MV-optimality of block designs having k≥v

In this paper we consider the problem of determining and constructing E- and MV-optimal block designs to use in experimental settings where treatments are applied to experimental units occurring in b blocks of size k, k. It is shown that some of the well-known methods for constructing E- and MV-optimal unequally replicated designs having k fail to yield optimal designs in the case where . Some sufficient conditions are derived for the E- and MV-optimality of block designs having and methods for constructing designs satisfying these sufficient conditions are given.     

Balanced ternary designs with block size three,any Λ and anyR

A balanced ternary design onV elements is a collection ofB blocks (which are multisets) of sizeK, such that each element occurs 0, 1 or 2 times per block andR times altogether, and such that each unordered pair of distinct elements occurs times. (For example, in the blockxxyyz, the pairxy is said to occur four times and the pairsxz, yz twice each.) It is straightforward to show that each element has to occur singly in a constant number of blocks, say ₁, and so each element also occurs twice in a constant number of blocks, say ₂, whereR= ₁+2 ₂. If ₂=0 the design is a balanced incomplete block design (binary design), so we assume ₂>0, andK<2V (corresponding to incompleteness in the binary case). Necessarily >1 if ₂>0 (andK>2).In 1980 and 1982 the author gave necessary and sufficient conditions for the existence of balanced ternary designs withK=3, =2 and ₂=1, 2 or 3. In this paper work on the existence of balanced ternary designs with block size three is concluded, in that necessary and sufficient conditions for the existence of a balanced ternary design withK=3, any >1 and any ₂ are given.     

Provable security of block ciphers against linear cryptanalysis: a mission impossible?

In this paper, we are concerned with the security of block ciphers against linear cryptanalysis and discuss the distance between the so-called practical security approach and the actual theoretical security provided by a given cipher. For this purpose, we present a number of illustrative experiments performed against small (i.e. computationally tractable) ciphers. We compare the linear probability of the best linear characteristic and the actual best linear probability (averaged over all keys). We also test the key equivalence hypothesis. Our experiments illustrate both that provable security against linear cryptanalysis is not achieved by present design strategies and the relevance of the practical security approach. Finally, we discuss the (im)possibility to derive actual design criteria from the intuitions underlined in these experiments. F.-X. Standaert is a Postdoctoral researcher of the Belgian Fund for Scientific Research (FNRS).