Search

On current computer architectures, GMRES' performance can be limited by its communication cost to generate orthonormal basis vectors of the Krylov subspace. To address this performance bottleneck, its $s$-step variant orthogonalizes a block of $s$ basis vectors at a time, potentially reducing the communication cost by a factor of $s$. Unfortunately, for a large step size $s$, the solver can generate extremely ill-conditioned basis vectors, and to maintain stability in practice, a conservatively small step size is used, which limits the performance of the $s$-step solver. To enhance the performance using a small step size, in this paper, we introduce a two-stage block orthogonalization scheme. Similar to the original scheme, the first stage of the proposed method operates on a block of $s$ basis vectors at a time, but its objective is to maintain the well-conditioning of the generated basis vectors with a lower cost. The orthogonalization of the basis vectors is delayed until the second stage when enough basis vectors are generated to obtain higher performance. Our analysis shows the stability of the proposed two-stage scheme. The performance is improved because while the same amount of computation as the original scheme is required, most of the communication is done at the second stage of the proposed scheme, reducing the overall communication requirements. Our performance results with up to 192 NVIDIA V100 GPUs on the Summit supercomputer demonstrate that when solving a 2D Laplace problem, the two-stage approach can reduce the orthogonalization time and the total time-to-solution by the respective factors of up to $2.6\times$ and $1.6\times$ over the original $s$-step GMRES, which had already obtained the respective speedups of $2.1\times$ and $1.8\times$ over the standard GMRES. Similar speedups were obtained for 3D problems and for matrices from the SuiteSparse Matrix Collection., Comment: Accepted for publication in IPDPS'24

New convergence bounds are presented for weighted, preconditioned, and deflated GMRES for the solution of large, sparse, non-Hermitian linear systems. These bounds are given for the case when the Hermitian part of the coefficient matrix is positive definite, the preconditioner is Hermitian positive definite, and the weight is equal to the preconditioner. The new bounds are a novel contribution in and of themselves. In addition, they are sufficiently explicit to indicate how to choose the preconditioner and the deflation space to accelerate the convergence. One such choice of deflating space is presented, and numerical experiments illustrate the effectiveness of such space.

CholeskyQR2 and shifted CholeskyQR3 are two state-of-the-art algorithms for computing tall-and-skinny QR factorizations since they attain high performance on current computer architectures. However, to guarantee stability, for some applications, CholeskyQR2 faces a prohibitive restriction on the condition number of the underlying matrix to factorize. Shifted CholeskyQR3 is stable but has $50\%$ more computational and communication costs than CholeskyQR2. In this paper, a randomized QR algorithm called Randomized Householder-Cholesky (\texttt{rand\_cholQR}) is proposed and analyzed. Using one or two random sketch matrices, it is proved that with high probability, its orthogonality error is bounded by a constant of the order of unit roundoff for any numerically full-rank matrix, and hence it is as stable as shifted CholeskyQR3. An evaluation of the performance of \texttt{rand\_cholQR} on a NVIDIA A100 GPU demonstrates that for tall-and-skinny matrices, \texttt{rand\_cholQR} with multiple sketch matrices is nearly as fast as, or in some cases faster than, CholeskyQR2. Hence, compared to CholeskyQR2, \texttt{rand\_cholQR} is more stable with almost no extra computational or memory cost, and therefore a superior algorithm both in theory and practice., Comment: 43 pages

We consider the problem of approximating the solution to $A(\mu) x(\mu) = b$ for many different values of the parameter $\mu$. Here we assume $A(\mu)$ is large, sparse, and nonsingular with a nonlinear dependence on $\mu$. Our method is based on a companion linearization derived from an accurate Chebyshev interpolation of $A(\mu)$ on the interval $[-a,a]$, $a \in \mathbb{R}$. The solution to the linearization is approximated in a preconditioned BiCG setting for shifted systems, where the Krylov basis matrix is formed once. This process leads to a short-term recurrence method, where one execution of the algorithm produces the approximation to $x(\mu)$ for many different values of the parameter $\mu \in [-a,a]$ simultaneously. In particular, this work proposes one algorithm which applies a shift-and-invert preconditioner exactly as well as an algorithm which applies the preconditioner inexactly. The competitiveness of the algorithms are illustrated with large-scale problems arising from a finite element discretization of a Helmholtz equation with parameterized material coefficient. The software used in the simulations is publicly available online, and thus all our experiments are reproducible.

We extend results known for the randomized Gauss-Seidel and the Gauss-Southwell methods for the case of a Hermitian and positive definite matrix to certain classes of non-Hermitian matrices. We obtain convergence results for a whole range of parameters describing the probabilities in the randomized method or the greedy choice strategy in the Gauss-Southwell-type methods. We identify those choices which make our convergence bounds best possible. Our main tool is to use weighted l1-norms to measure the residuals. A major result is that the best convergence bounds that we obtain for the expected values in the randomized algorithm are as good as the best for the deterministic, but more costly algorithms of Gauss-Southwell type. Numerical experiments illustrate the convergence of the method and the bounds obtained. Comparisons with the randomized Kaczmarz method are also presented.

This paper defines double fibrations (fibrations of double categories) and describes their key examples and properties. In particular, it shows how double fibrations relate to existing fibrational notions such as monoidal fibrations and discrete double fibrations, proves a representation theorem for double fibrations, and shows how double fibrations are a type of internal fibration., Comment: 59 pages

We study the interaction between the notions of filteredness, fractions and fibrations in the theory of bicategories, generalizing classical results for categories. We give an explicit formula for filtered pseudo-colimits of categories indexed by a bicategory, and we use it to compute the hom-categories of a bicategory of fractions. As a consequence, we show that the canonical pseudo-functor into a bicategory of fractions is exact.

We discuss different cases of dissipative Hamiltonian differential-algebraic equations and the linear algebraic systems that arise in their linearization or discretization. For each case we give examples from practical applications. An important feature of the linear algebraic systems is that the (non-Hermitian) system matrix has a positive definite or semidefinite Hermitian part. In the positive definite case we can solve the linear algebraic systems iteratively by Krylov subspace methods based on efficient three-term recurrences. We illustrate the performance of these iterative methods on several examples. The semidefinite case can be challenging and requires additional techniques to deal with "singular part", while the "positive definite part" can still be treated with the three-term recurrence methods.

In this paper, we extend to the block case, the a posteriori bound showing superlinear convergence of Conjugate Gradients developed in [J. Comput. Applied Math., 48 (1993), pp. 327-341]; that is, we obtain similar bounds, but now for block Conjugate Gradients. We also present a series of computational experiments illustrating the validity of the bound developed here, as well as the bound from [SIAM Review, 47 (2005), pp. 247-272] using angles between subspaces. Using these bounds, we make some observations on the onset of superlinearity, and how this onset depends on the eigenvalue distribution and the block size., Comment: 21 pages, 14 figures

We consider asynchronous versions of the first and second order Richardson methods for solving linear systems of equations. These methods depend on parameters whose values are chosen a priori. We explore the parameter values that can be proven to give convergence of the asynchronous methods. This is the first such analysis for asynchronous second order methods. We find that for the first order method, the optimal parameter value for the synchronous case also gives an asynchronously convergent method. For the second order method, the parameter ranges for which we can prove asynchronous convergence do not contain the optimal parameter values for the synchronous iteration. In practice, however, the asynchronous second order iterations may still converge using the optimal parameter values, or parameter values close to the optimal ones, despite this result. We explore this behavior with a multithreaded parallel implementation of the asynchronous methods., Comment: 15 pages

Dense particulate suspensions can not only increase their viscosity and shear thicken under external forcing, but also jam into a solid-like state that is fully reversible when the force is removed. An impact on the surface of a dense suspension can trigger this jamming process by generating a shear front that propagates into the bulk of the system. Tracking and visualizing such a front is difficult because suspensions are optically opaque and the front can propagate as fast as several meters per second. Recently, high-speed ultrasound imaging has been used to overcome this problem and extract two-dimensional sections of the flow field associated with jamming front propagation. Here we extend this method to reconstruct the three-dimensional flow field. This enables us to investigate the evolution of jamming fronts for which axisymmetry cannot be assumed, such as impact at angles tilted away from the normal to the free surface of the suspension. We find that sufficiently far from solid boundaries the resulting flow field is approximately identical to that generated by normal impact, but rotated and aligned with the angle of impact. However, once the front approaches the solid boundary at the bottom of the container, it generates a squeeze flow that deforms the front profile and causes jamming to proceed in a non-axisymmetric manner., Comment: 12 pages, 11 figures

We give a unified direct proof of the lifting of PIE limits to the 2-category of algebras and (pseudo) morphisms, which specifies precisely which of the projections of the lifted limit are strict and detect strictness. In the literature, these limits were lifted one by one, so as to keep track of these projections in each case. We work in the more general context of weak algebra morphisms, so as to include lax morphisms as well. PIE limits are also all simultaneously lifted in this case, provided some specified arrows of the diagram are pseudo morphisms. Again, this unifies the previously known lifting of many particular PIE limits, which were also treated separately., Comment: 11 pages

We give the definitions of model bicategory and $q$-homotopy, which are natural generalizations of the notions of model category and homotopy to the context of bicategories. For any model bicategory $\mathcal{C}$, denote by $\mathcal{C}_{fc}$ the full sub-bicategory of the fibrant-cofibrant objects. We prove that the 2-dimensional localization of $\mathcal{C}$ at the weak equivalences can be computed as a bicategory $\mathcal{H}o(\mathcal{C})$ whose objects and arrows are those of $\mathcal{C}_{fc}$ and whose 2-cells are classes of $q$-homotopies up to an equivalence relation. When considered for a model category, $q$-homotopies coincide with the homotopies as considered by Quillen. The pseudofunctor $\mathcal{C} \stackrel{q}{\longrightarrow} \mathcal{H}o(\mathcal{C})$ which yields the localization is constructed by using a notion of fibrant-cofibrant replacement in this context. We include an appendix with a general result of independent interest on a transfer of structure for lax functors, that we apply to obtain a pseudofunctor structure for the fibrant-cofibrant replacement., Comment: Final version, to appear in Advances in Mathematics

Given a bicategory C and a family W of arrows of C, we give conditions on the pair (C,W) that allow us to construct the bicategorical localization with respect to W by dealing only with the 2-cells, that is without adding objects or arrows to C. We show that in this case, the 2-cells of the localization can be given by the homotopies with respect to W, a notion defined in this article which is closely related to Quillen's notion of homotopy for model categories but depends only on a single family of arrows. This localization result has a natural application to the construction of the homotopy bicategory of a model bicategory, which we develop elsewhere, as the pair (C_{fc},W) given by the weak equivalences between fibrant-cofibrant objects satisfies the conditions given in the present article.

We define a homotopy relation between arrows of a category with weak equivalences, and give a condition under which the quotient by the homotopy relation yields the homotopy category. In the case of the fibrant-cofibrant objects of a model category this condition holds, and we show that our notion of homotopy coincides with the classical one. We also show that Quillen's construction of the homotopy category of a model category, in which the arrows are homotopical classes of a single arrow between fibrant-cofibrant objects, can be made as well for categories with weak equivalences using this notion of homotopy. We deduce from our work the saturation of model categories. The proofs of these results, which consider only the weak equivalences, become simpler (as it is usually the case) than those who involve the whole structure of a model category.

We give a definition of weak morphism of $T$-algebras, for a $2$-monad $T$, with respect to an arbitrary family $\Omega$ of $2$-cells of the base $2$-category. By considering particular choices of $\Omega$, we recover the concepts of lax, pseudo and strict morphisms of $T$-algebras. We give a general notion of weak limit, and define what it means for such a limit to be compatible with another family of $2$-cells. These concepts allow us to prove a limit lifting theorem which unifies and generalizes three different previously known results of $2$-dimensional monad theory. Explicitly, by considering the three choices of $\Omega$ above our theorem has as corollaries the lifting of oplax (resp. $\sigma$, which generalizes lax and pseudo, resp. strict) limits to the $2$-categories of lax (resp. pseudo, resp. strict) morphisms of $T$-algebras., Comment: minor changes from v1, 17 pages

In this paper we introduce sigma limits (which we write $\sigma$-limits), a concept that interpolates between lax and pseudolimits: for a fixed family $\Sigma$ of arrows of a 2-category $\mathcal{A}$, a $\sigma$-cone for a $2$-functor $\mathcal{A} \stackrel{F}{\rightarrow} \mathcal{B}$ is a lax cone such that the structural 2-cells corresponding to the arrows of $\Sigma$ are invertible. The conical $\sigma$-limit of $F$ is the universal $\sigma$-cone. Similary we define $\sigma$-natural transformations and weighted $\sigma$-limits. We consider also the case of bilimits. We develop the theory of $\sigma$-limits and $\sigma$-bilimits, whose importance relies on the following key fact: any weighted $\sigma$-limit (or $\sigma$-bilimit) can be expressed as a conical one. From this we obtain, in particular, a canonical expression of an arbitrary $\mathcal{C}at$-valued 2-functor as a conical $\sigma$-bicolimit of representable 2-functors, for a suitable choice of $\Sigma$, which is equivalent to the well known bicoend formula. As an application, we establish the 2-dimensional theory of flat pseudofunctors. We define a $\mathcal{C}at$-valued pseudofunctor to be flat when its left bi-Kan extension along the Yoneda 2-functor preserves finite weighted bilimits. We introduce a notion of 2-filteredness of a 2-category with respect to a class $\Sigma$, which we call $\sigma$-filtered. Our main result is: A pseudofunctor $\mathcal{A} \rightarrow \mathcal{C}at$ is flat if and only if it is a $\sigma$-filtered $\sigma$-bicolimit of representable 2-functors. In particular the reader will notice the relevance of this result for the development of a theory of 2-topoi., Comment: 40 pages, final version to appear in Advances in Mathematics

Given a 2-category $\mathcal{A}$, a $2$-functor $\mathcal{A} \overset {F} {\longrightarrow} \mathcal{C}at$ and a distinguished 1-subcategory $\Sigma \subset \mathcal{A}$ containing all the objects, a $\sigma$-cone for $F$ (with respect to $\Sigma$) is a lax cone such that the structural $2$-cells corresponding to the arrows of $\Sigma$ are invertible. The conical $\sigma$-limit is the universal (up to isomorphism) $\sigma$-cone. The notion of $\sigma$-limit generalises the well known notions of pseudo and lax limit. We consider the fundamental notion of $\sigma$-filtered} pair $(\mathcal{A}, \, \Sigma)$ which generalises the notion of 2-filtered 2-category. We give an explicit construction of $\sigma$-filtered $\sigma$-colimits of categories, construction which allows computations with these colimits. We then state and prove a basic exactness property of the 2-category of categories, namely, that $\sigma$-filtered $\sigma$-colimits commute with finite weighted pseudo (or bi) limits. An important corollary of this result is that a $\sigma$-filtered $\sigma$-colimit of exact category valued 2-functors is exact. This corollary is essential in the 2-dimensional theory of flat and pro-representable 2-functors, that we develop elsewhere., Comment: 20 pages, many 2-cell diagrams

We propose a block Krylov subspace version of the GCRO-DR method proposed in [Parks et al. SISC 2005], which is an iterative method allowing for the efficient minimization of the the residual over an augmented block Krylov subspace. We offer a clean derivation of the method and discuss methods of selecting recycling subspaces at restart as well as implementation decisions in the context of high-performance computing. Numerical experiments are split into those demonstrating convergence properties and those demonstrating the data movement and cache efficiencies of the dominant operations of the method, measured using processor monitoring code from Intel., Comment: 29 pages, 18 pages of manuscript text, 15 figures, 1 table, Temple University Research Report 16-04-04

An implementation of GMRES with multiple preconditioners (MPGMRES) is proposed for solving shifted linear systems with shift-and-invert preconditioners. With this type of preconditioner, the Krylov subspace can be built without requiring the matrix-vector product with the shifted matrix. Furthermore, the multipreconditioned search space is shown to grow only linearly with the number of preconditioners. This allows for a more efficient implementation of the algorithm. The proposed implementation is tested on shifted systems that arise in computational hydrology and the evaluation of different matrix functions. The numerical results indicate the effectiveness of the proposed approach., Comment: 24 pages, 4 figures, 1 table

We consider locales $B$ as algebras in the tensor category $s\ell$ of sup-lattices. We show the equivalence between the Joyal-Tierney descent theorem for open localic surjections $sh(B) \stackrel{q}{\longrightarrow} \mathcal{E}$ in Galois theory [An extension of the Galois Theory of Grothendieck, AMS Memoirs 151] and a Tannakian recognition theorem over $s\ell$ for the $s\ell$-functor $Rel(E) \stackrel{Rel(q^*)}{\longrightarrow} Rel(sh(B)) \cong (B$-$Mod)_0$ into the $s\ell$-category of discrete $B$-modules. Thus, a new Tannaka recognition theorem is obtained, essentially different from those known so far. This equivalence follows from two independent results. We develop an explicit construction of the localic groupoid $G$ associated by Joyal-Tierney to $q$, and do an exhaustive comparison with the Deligne Tannakian construction of the Hopf algebroid $L$ associated to $Rel(q^*)$, and show they are isomorphic, that is, $L \cong \mathcal{O}(G)$. On the other hand, we show that the $s\ell$-category of relations of the classifying topos of any localic groupoid $G$, is equivalent to the $s\ell$-category of $L$-comodules with discrete subjacent $B$-module, where $L = \mathcal{O}(G)$. We are forced to work over an arbitrary base topos because, contrary to the neutral case developed over Sets in [A Tannakian Context for Galois Theory, Advances in Mathematics 234], here change of base techniques are unavoidable., Comment: arXiv admin note: substantial text overlap with arXiv:1507.04772

The main result of this thesis is the construction of a tannakian context over the category of sup-lattices, associated with an arbitrary Grothendieck topos, and the attainment of new results in tannakian representation theory from it. Although many results were obtained and published historically linking Galois and Tannaka theory (see our introduction), these are different and less general since they assume the existence of Galois closures and work on Galois topos rather than on arbitrary topos. Instead we, when talking about Galois theory, mean the extension to arbitrary topos of Joyal and Tierney, critical to get the results of this thesis. The tannakian context associated with a Grothendieck topos is obtained through the process of taking relations of its localic cover. Then, through an investigation and exhaustive comparison of the constructions of the Galois and Tannaka theories, we prove the equivalence of their fundamental recognition theorems (see section 8). Since the (bi)categories of relations of a Grothendieck topos were characterized by Carboni and Walters, a new recognition-type tannakian theorem (theorem 8.12) is obtained, essentially different from those known so far., Comment: this is my PhD thesis, written under the supervision of E. J. Dubuc

We consider the solution of large-scale nonlinear algebraic Hermitian eigenproblems of the form $T(\lambda)v=0$ that admit a variational characterization of eigenvalues. These problems arise in a variety of applications and are generalizations of linear Hermitian eigenproblems $Av\!=\!\lambda Bv$. In this paper, we propose a Preconditioned Locally Minimal Residual (PLMR) method for efficiently computing interior eigenvalues of problems of this type. We discuss the development of search subspaces, preconditioning, and eigenpair extraction procedure based on the refined Rayleigh-Ritz projection. Extension to the block methods is presented, and a moving-window style soft deflation is described. Numerical experiments demonstrate that PLMR methods provide a rapid and robust convergence towards interior eigenvalues. The approach is also shown to be efficient and reliable for computing a large number of extreme eigenvalues, dramatically outperforming standard preconditioned conjugate gradient methods.

We study the use of Krylov subspace recycling for the solution of a sequence of slowly-changing families of linear systems, where each family consists of shifted linear systems that differ in the coefficient matrix only by multiples of the identity. Our aim is to explore the simultaneous solution of each family of shifted systems within the framework of subspace recycling, using one augmented subspace to extract candidate solutions for all the shifted systems. The ideal method would use the same augmented subspace for all systems and have fixed storage requirements, independent of the number of shifted systems per family. We show that a method satisfying both requirements cannot exist in this framework. As an alternative, we introduce two schemes. One constructs a separate deflation space for each shifted system but solves each family of shifted systems simultaneously. The other builds only one recycled subspace and constructs approximate corrections to the solutions of the shifted systems at each cycle of the iterative linear solver while only minimizing the base system residual. At convergence of the base system solution, we apply the method recursively to the remaining unconverged systems. We present numerical examples involving systems arising in lattice quantum chromodynamics., Comment: 5 figures, 20 pages (main paper 18 pages + refs 2 pages)

Strong similarities have been long observed between the Galois (Categories Galoisiennes) and the Tannaka (Categories Tannakiennes) theories of representation of groups. In this paper we construct an explicit (neutral) Tannakian context for the Galois theory of atomic topoi, and prove the equivalence between its fundamental theorems. Since the theorem is known for the Galois context, this yields, in particular, a proof of the fundamental (recognition) theorem for a new Tannakian context. This example is different from the additive cases or their generalization, where the theorem is known to hold, and where the unit of the tensor product is always an object of finite presentation, which is not the case in our context., Comment: This is a revision. We switch some of the proofs to another level of abstraction. We generalized the equivalence between the Tannaka and the Galois recognition theorems from atomic to arbritrary topoi. We strengthened the result "The Tannaka lifting functor is an equivalence" for atomic topos to "The Tannaka lifting functor is an equivalence if and only if the topos is atomic"

The purpose of this work is twofold: to expose the existing similarities between the generalizations of the Tannaka and Galois theories, and on the other hand, to develop in detail our own treatment of part of the content of Joyal and Street [1] paper, generalizing from vector spaces to an abstract tensor category. We also develop in detail the proof of the Tannaka equivalence of categories in the case of vector spaces. Saavedra Rivano [2], Deligne and Milne [3] generalize classical Tannaka theory to the context of K-linear tensor (or monoidal) categories. They obtain a lifting-equivalence into a category of \group representations" for a finite-dimensional vector space valued monoidal functor. This lifting theorem is similar to the one of Grothendieck Galois theory [4] for a finite sets valued functor. On the other hand, Joyal and Street [1] work on the algebraic side of the duality between algebra and geometry, and also obtain a lifting-equivalence, but now to the category of finite-dimensional comodules over a Hopf algebra. In this work we follow the ideas of Joyal and Street and prove their lifting-equivalence, and then we show how it corresponds, by dualizing, to the ones of Saavedra Rivano [2] and Deligne and Milne [3]. Text is in spanish, but a brief english introduction is provided., Comment: This is my "tesis de licenciatura" for the University of Buenos Aires, from the year 2009

There are several ideas being used today for Web information retrieval, and specifically in Web search engines. The PageRank algorithm is one of those that introduce a content-neutral ranking function over Web pages. This ranking is applied to the set of pages returned by the Google search engine in response to posting a search query. PageRank is based in part on two simple common sense concepts: (i)A page is important if many important pages include links to it. (ii)A page containing many links has reduced impact on the importance of the pages it links to. In this paper we focus on asynchronous iterative schemes to compute PageRank over large sets of Web pages. The elimination of the synchronizing phases is expected to be advantageous on heterogeneous platforms. The motivation for a possible move to such large scale distributed platforms lies in the size of matrices representing Web structure. In orders of magnitude: $10^{10}$ pages with $10^{11}$ nonzero elements and $10^{12}$ bytes just to store a small percentage of the Web (the already crawled); distributed memory machines are necessary for such computations. The present research is part of our general objective, to explore the potential of asynchronous computational models as an underlying framework for very large scale computations over the Grid. The area of ``internet algorithmics'' appears to offer many occasions for computations of unprecedent dimensionality that would be good candidates for this framework., Comment: 8 pages to appear at ParCo2005 Conference Proceedings