|
SIAM Review
Journal Prestige (SJR): 2.273  Citation Impact (citeScore): 4 Number of Followers: 9  Hybrid journal * Containing 1  Open Access article(s) in this issue *ISSN (Print) 0036-1445 - ISSN (Online) 1095-7200 Published by Society for Industrial and Applied Mathematics  [17 journals]
|
- Survey and Review
-
Free pre-print version: Loading...
Authors: J. M. Sanz-Serna
Pages: 515 - 515
Abstract: SIAM Review, Volume 64, Issue 3, Page 515-515, August 2022.
This issue contains two Survey and Review papers. The first, by Qinmeng Zou and Frédéric Magoulès, is “Delayed Gradient Methods for Symmetric and Positive Definite Linear Systems.” Gradient methods are the oldest and simplest algorithms to minimize a real objective function (f(x)). The ((n+1))st approximation to the minimizer is defined as (x_n+1 = x_n -\alpha_n g_n), where \(g_n\) is the gradient (\nabla f(x_n)) and (\alpha_n>0) is a steplength that depends on the specific method being used. Old and simple as the idea may be, gradient algorithms are of much current interest in the literature; for instance, they played a major role in the influential survey devoted to optimization in machine learning published in Volume 60, Issue 2 of this journal. The paper by Zou and Magoulès focuses on the quadratic case $f(x) = (1/2)x^TAx-b^Tx$ ($A$ symmetric and positive definite), where finding the minimizer is of course equivalent to solving the linear system $Ax=b$ and the gradient $g_n$ coincides with the residual $Ax_n-b$. Well-known strategies to determine the steplength include steepest descent, where $\alpha_n$ is chosen so as to minimize $f(x_{n+1})$, and minimal gradient (or minimal residual), where one rather minimizes the length of $g_{n+1}$. In both of these strategies, the value of $\alpha_n$ depends only on $g_n$. The term “delayed” in the title of the article refers to methods where the recipe to determine $\alpha_n$ includes information from past gradients $g_{n-1}, g_{n-2}$, \dots, and/or past stepsizes $\alpha_{n-1}$, $\alpha_{n-2}$, \dots. The numerical experiments reported clearly indicate that such delayed strategies may give rise to algorithms that are competitive with conjugate gradient methods in large ill-conditioned problems. The paper presents a neat summary of the recent results in this area and of the techniques used to derive them. Mark Van der Boor, Sem C. Borst, Johan S. H. Van Leeuwaarden, and Debankur Mukherjee are the authors of the second paper, “Scalable Load Balancing in Networked Systems: A Survey of Recent Advances.” The problem under consideration is as follows. A dispatcher receives clients that arrive randomly, and her job is to direct them to one of $N\gg 1$ servers. The time required by each client to be served is also random, so that a queue (of random length) of waiting clients will be formed at each server. How should the dispatcher proceed to expedite the service' As one would expect in these days of cloud networks and data systems with massive number of individual centers, the problem is currently receiving much attention in the literature. A strategy that suggests itself is the so-called “join the shortest queue” (JSQ), where on their arrival clients are directed to the server having the shortest queue. While JSQ has been proved to possess several favorable properties, it may not be the best option, due to communication overheads: each time a client arrives, the dispatcher has to communicate with all servers to find the lengths of their queues. The paper analyzes, in the limit $N\rightarrow \infty$, many alternative strategies. Nonspecialists will have little difficulty in reading the easily accessible first few sections and may be interested in discovering how even small tweaks in the algorithms may result in substantial improvements of their performance.
Citation: SIAM Review
PubDate: 2022-08-04T07:00:00Z
DOI: 10.1137/22N975500
Issue No: Vol. 64, No. 3 (2022)
-
- Delayed Gradient Methods for Symmetric and Positive Definite Linear
Systems-
Free pre-print version: Loading...
Authors: Qinmeng Zou, Frédéric Magoulès
Pages: 517 - 553
Abstract: SIAM Review, Volume 64, Issue 3, Page 517-553, August 2022.
The primary aim of this paper is to provide a review of the last few decades of research focused on delayed gradient methods for solving symmetric positive definite linear systems. Recent developments on spectral properties are stressed, as well as their implications for the formulation of new methods. Numerical experiments are conducted with emphasis on the comparison with the conjugate gradient method for solving ill-conditioned problems.
Citation: SIAM Review
PubDate: 2022-08-04T07:00:00Z
DOI: 10.1137/20M1321140
Issue No: Vol. 64, No. 3 (2022)
-
- Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
-
Free pre-print version: Loading...
Authors: Mark Van der Boor, Sem C. Borst, Johan S. H. Van Leeuwaarden, Debankur Mukherjee
Pages: 554 - 622
Abstract: SIAM Review, Volume 64, Issue 3, Page 554-622, August 2022.
In this survey we provide an overview of recent advances on scalable load balancing schemes which provide favorable delay performance and yet require minimal implementation overhead. The basic load balancing scenario involves a single dispatcher where tasks arrive that must immediately be forwarded to one of $N$ single-server queues. The join-the-shortest-queue (JSQ) policy yields vanishing delays as $N$ grows large, as in a centralized queuing arrangement, but involves a prohibitive communication burden. In contrast, JSQ($d$) schemes that assign an incoming task to a server with the shortest queue among $d$ servers selected uniformly at random require little communication, but lead to constant delays. In order to examine this fundamental trade-off between delay performance and implementation overhead, we discuss a body of recent research on JSQ($d(N)$) schemes in which the diversity parameter $d(N)$ depends on $N$ and investigate the growth rate of $d(N)$ required to match the optimal JSQ performance on fluid and diffusion scales. Stochastic coupling techniques and scaling limits play an instrumental role in establishing this asymptotic optimality. We demonstrate how this methodology carries over to infinite-server settings, finite buffers, multiple dispatchers, servers arranged on graph topologies, and token-based load balancing schemes such as join-the-idle-queue (JIQ), thus providing a broad overview of the main trends in the field.
Citation: SIAM Review
PubDate: 2022-08-04T07:00:00Z
DOI: 10.1137/20M1323746
Issue No: Vol. 64, No. 3 (2022)
-
- Research Spotlights
-
Free pre-print version: Loading...
Authors: Misha E. Kilmer
Pages: 623 - 624
Abstract: SIAM Review, Volume 64, Issue 3, Page 623-624, August 2022.
What's in a name [brand]' In the first of three Research Spotlights articles this issue, authors Joseph D. Johnson, Adam M. Redlich, and Daniel M. Abrams address this issue by developing a mathematical model for the dynamics of competition through advertising. Specifically, in “A Mathematical Model for the Origin of Name Brands and Generics," readers are presented with a mathematical model for the dynamics of competition through advertising. Here, the terms “generic” and “name brand” refer to low and high advertising investment states, respectively. A distinguishing feature of the approach taken by the authors in this work is that they model “monopolistic competition," meaning that although there may be many suppliers of a product/service, these are distinguished only by brand and/or quality. The analysis of the existence and stability of equilibria of their ordinary differential equation system model predicts that “when advertising is relatively cheap compared to the benefit of advertising," these two advertising investment states will arise. This segmentation “contrasts starkly with (often implicit) assumptions of smooth, singly peaked functions for economic metrics." The authors note that their model predicts that segmentation should be reflected in price distributions. Indeed, although there are limitations in their model which readers are invited to consider addressing in future work, they show good qualitative agreement to this prediction on a large consumer data set. The need to solve linear least squares problems is ubiquitous in science and engineering applications, and it is at the heart of our second article, “Some Comments on Preconditioning for Normal Equations and Least Squares," authored by Andy Wathen. Iterative solvers are often preferred over direct methods for large-scale least squares as they require only the ability to perform matrix-vector products with the system matrix and its (conjugate) transpose. A preconditioner, which is an approximation to the original matrix with desirable properties (e.g., easy to apply, easy to “invert''), is usually employed to speed convergence. To be effective, the spectrum of the preconditioned normal equations operator should be appropriately clustered. Using several concrete examples as motivation, the author explores a subtle and underappreciated difficulty in designing preconditioners for least squares problems called the “matrix squaring problem." Simply put, a good approximation, $P$, to the original matrix, $B$, may not translate into having an effective preconditioner, $P^T P$, for the normal equations matrix $B^T B$. The article includes theory and discussion about when the matrix squaring problem can be expected versus when it is a nonissue in the case of invertible matrices. The author's final example shows that the matrix squaring problem can occur even in the full rank rectangular case, which should serve as a warning to practitioners that, indeed, it may not be sufficient to seek approximations to the original operator in the design of an effective preconditioner for iterative solution to the least squares problem. The final article, “Hypergraph Cuts with General Splitting Functions," by Nate Veldt, Austin R. Benson, and Jon Kleinberg, tackles a problem that is central to the study of hypergraphs. While readers may be familiar with a standard graph representation in which an edge connects exactly two vertices, in a hypergraph, an edge (a.k.a. hyperedge) refers to a grouping of (possibly) more than two vertices. This extra dimensionality associated to an edge complicates the generalization of graph splitting to hypergraphs, a fact that can be appreciated by studying the graphical illustrations provided in the article. Nevertheless, the authors provide a framework for hypergraph cuts that leads to a rich set of results and illuminates new research questions. Specifically, their framework utilizes so-called “splitting functions" which assign a penalty to each rearrangement of a hyperedge's nodes. These functions enable them to characterize the minimum $s$-$t$ cut problem of finding a minimum weight set of hyperedges to cut in order to separate (e.g., as might be required in data clustering applications) nodes $s$ and $t$ from each other. The paper contains many new contributions, among them algorithms for some variants of the hypergraph $s$-$t$ cut problem that are polynomial time and theoretical results on the NP-hardness of other variants. As this article “includes broad contributions at the intersection of graph theory, optimization, scientific computing, and other subdisciplines in applied mathematics," and offers several suggestions for follow-up research questions, it is likely to appeal to many SIREV readers.
Citation: SIAM Review
PubDate: 2022-08-04T07:00:00Z
DOI: 10.1137/22N975512
Issue No: Vol. 64, No. 3 (2022)
-
- A Mathematical Model for the Origin of Name Brands and Generics
-
Free pre-print version: Loading...
Authors: Joseph D. Johnson, Adam M. Redlich, Daniel M. Abrams
Pages: 625 - 639
Abstract: SIAM Review, Volume 64, Issue 3, Page 625-639, August 2022.
Firms in the U.S. spend over $200 billion each year advertising their products to consumers, around one percent of the country's gross domestic product. It is of great interest to understand how that aggregate expenditure affects prices, market efficiency, and overall welfare. Here, we present a mathematical model for the dynamics of competition through advertising and find a surprising prediction: when advertising is relatively cheap compared to the maximum benefit advertising offers, rational firms split into two groups, one with significantly less advertising (a “generic” group) and one with significantly more advertising (a “name-brand” group). Our model predicts that this segmentation will also be reflected in price distributions; we use large consumer data sets to test this prediction and find good qualitative agreement.
Citation: SIAM Review
PubDate: 2022-08-04T07:00:00Z
DOI: 10.1137/20M1360888
Issue No: Vol. 64, No. 3 (2022)
-
- Some Comments on Preconditioning for Normal Equations and Least Squares
-
Free pre-print version: Loading...
Authors: Andy Wathen
Pages: 640 - 649
Abstract: SIAM Review, Volume 64, Issue 3, Page 640-649, August 2022.
The solution of systems of linear(ized) equations lies at the heart of many problems in scientific computing. In particular, for large systems, iterative methods are a primary approach. For many symmetric (or self-adjoint) systems, there are effective solution methods based on the conjugate gradient method (for definite problems) or MINRES (for indefinite problems) in combination with an appropriate preconditioner, which is required in almost all cases. For nonsymmetric systems there are two principal lines of attack: the use of a nonsymmetric iterative method such as GMRES or transformation into a symmetric problem via the normal equations and application of LSQR. In either case, an appropriate preconditioner is generally required. We consider the possibilities here, particularly the idea of preconditioning the normal equations via approximations to the original nonsymmetric matrix. We highlight dangers that readily arise in this approach. Our comments also apply in the context of linear least squares problems.
Citation: SIAM Review
PubDate: 2022-08-04T07:00:00Z
DOI: 10.1137/20M1387948
Issue No: Vol. 64, No. 3 (2022)
-
- Hypergraph Cuts with General Splitting Functions
-
Free pre-print version: Loading...
Authors: Nate Veldt, Austin R. Benson, Jon Kleinberg
Pages: 650 - 685
Abstract: SIAM Review, Volume 64, Issue 3, Page 650-685, August 2022.
The minimum $s$-$t$ cut problem in graphs is one of the most fundamental problems in combinatorial optimization, and graph cuts underlie algorithms throughout discrete mathematics, theoretical computer science, operations research, and data science. While graphs are a standard model for pairwise relationships, hypergraphs provide the flexibility to model multiway relationships and are now a standard model for complex data and systems. However, when generalizing from graphs to hypergraphs, the notion of a “cut hyperedge” is less clear, as a hyperedge's nodes can be split in several ways. Here, we develop a framework for hypergraph cuts by considering the problem of separating two terminal nodes in a hypergraph in a way that minimizes a sum of penalties at split hyperedges. In our setup, different ways of splitting the same hyperedge have different penalties, and the penalty is encoded by what we call a splitting function. Our framework opens a rich space on the foundations of hypergraph cuts. We first identify a natural class of cardinality-based hyperedge splitting functions that depend only on the number of nodes on each side of the split. In this case, we show that the general hypergraph $s$-$t$ cut problem can be reduced to a tractable graph $s$-$t$ cut problem if and only if the splitting functions are submodular. We also identify a wide regime of non-submodular splitting functions for which the problem is NP-hard. Finally, we outline several open questions on general hypergraph cut problems.
Citation: SIAM Review
PubDate: 2022-08-04T07:00:00Z
DOI: 10.1137/20M1321048
Issue No: Vol. 64, No. 3 (2022)
-
- SIGEST
-
Free pre-print version: Loading...
Authors: The Editors
Pages: 687 - 687
Abstract: SIAM Review, Volume 64, Issue 3, Page 687-687, August 2022.
In this section we present “Minimizing the Repayment Cost of Federal Student Loans,” by Paolo Guasoni and Yu-Jui Huang. This is the highlighted SIGEST version of an article that first appeared in the SIAM Journal on Financial Mathematics (SIFIN) in 2021. The article studies optimal strategies for repayment of federal student loans in the USA. These loans, which can be used to cover tuition and living expenses, have specific features that make them tricky to evaluate. Sections 2 and 4, as in the original SIFIN article, take account of two key student loan features: capping repayment levels at a proportion of current income, and forgiving the debt after a sufficiently long period of good standing. Sections 3 and 5, which are new to the revised SIGEST version, give results that incorporate a third feature: the effect of simple interest. The modeling and analysis presented here shed light on an important, mathematically challenging financial product and give practical insights into a complicated and potentially daunting set of choices available to those who must negotiate their way through these contracts.
Citation: SIAM Review
PubDate: 2022-08-04T07:00:00Z
DOI: 10.1137/21N975527
Issue No: Vol. 64, No. 3 (2022)
-
- Minimizing the Repayment Cost of Federal Student Loans
Open Access Article-
Free pre-print version: Loading...
Authors: Paolo Guasoni, Yu-Jui Huang
Pages: 689 - 709
Abstract: SIAM Review, Volume 64, Issue 3, Page 689-709, August 2022.
Federal student loans are fixed-rate debt contracts with three main special features: (i) borrowers can use income-driven schemes to make payments proportional to their income above subsistence; (ii) after several years of being in good standing, the remaining balance is forgiven but taxed as ordinary income; and (iii) accrued interest is simple, i.e., not capitalized. For a very small loan, the cost-minimizing repayment strategy dictates maximum payments until full repayment, forgoing both income-driven schemes and forgiveness. For a very large loan, the minimal payments allowed by income-driven schemes are optimal. For intermediate balances, the optimal repayment strategy may entail an initial period of minimum payments to exploit the noncapitalization of accrued interest, but when the principal is being reimbursed maximal payments always precede minimum payments. Income-driven schemes and simple accrued interest mostly benefit borrowers with very large balances.
Citation: SIAM Review
PubDate: 2022-08-04T07:00:00Z
DOI: 10.1137/22M1505840
Issue No: Vol. 64, No. 3 (2022)
-
- Education
-
Free pre-print version: Loading...
Authors: Darinka Dentcheva
Pages: 711 - 712
Abstract: SIAM Review, Volume 64, Issue 3, Page 711-712, August 2022.
This issue of SIAM Review presents two papers in the Education section. The first paper, “Deforming $\ \cdot\ _1$ into $\ \cdot\ _\infty$ via Polyhedral Norms: A Pedestrian Approach,” is contributed by Manlio Gaudioso and Jean-Baptiste Hiriart-Urruty. The paper starts from the well-known properties of the $\ell_p$-norms in the Euclidean space $\mathbb{R}^n$. For $x\in\mathbb{R}^n$ and $p\geq 1$, the norm is given by $\ x\ _p=\big(\sum_{i=1}^n x_i ^p\big)^\frac{1}{p}$ with the limiting case $p\to\infty$ providing the norm $\ x\ _\infty=\max_{1\leq i\leq n} x_i .$ The unit balls determined by the norms for $p=1$ and $p=\infty$ are polyhedral, while for $p\in (1,\infty)$ the unit ball has a smooth surface. Furthermore, the unit balls become larger when $p$ grows. One can represent the polyhedral norms (for $p=1$ or $p=\infty$) as maxima of linear forms, and this observation motivates the following notion. For an integer $k$ with value between 1 and $n$, we define the following real-valued function: \[ N_k(x)=\max\ x_i_1 + x_i_2 +\dots+ x_i_k : 1łeq i_1
Citation: SIAM Review
PubDate: 2022-08-04T07:00:00Z
DOI: 10.1137/22N975536
Issue No: Vol. 64, No. 3 (2022)
-
- Deforming $ . _{1}$ into $ . _{\infty}$ via Polyhedral Norms: A Pedestrian
Approach-
Free pre-print version: Loading...
Authors: Manlio Gaudioso, Jean-Baptiste Hiriart-Urruty
Pages: 713 - 727
Abstract: SIAM Review, Volume 64, Issue 3, Page 713-727, August 2022.
We consider, and study with elementary calculus, the polyhedral norms $ x _{(k)}=$ sum of the $\mathit{k}$ largest among the $ x_{i} $'s. Besides their basic properties, we provide various expressions of the unit balls associated with them and determine all the facets and vertices of these balls. We do the same with the dual norm $ . _{(k)}^{\ast }$ of $ . _{(k)}$. The study of these polyhedral norms is motivated, among other reasons, by the necessity of handling sparsity in some modern optimization problems, as is explained at the end of the paper.
Citation: SIAM Review
PubDate: 2022-08-04T07:00:00Z
DOI: 10.1137/21M1391481
Issue No: Vol. 64, No. 3 (2022)
-
- Analyzing Pattern Formation in the Gray--Scott Model: An XPPAUT Tutorial
-
Free pre-print version: Loading...
Authors: Demi L. Gandy, Martin R. Nelson
Pages: 728 - 747
Abstract: SIAM Review, Volume 64, Issue 3, Page 728-747, August 2022.
The Gray--Scott model is a widely studied autocatalytic model that exhibits a range of interesting pattern formation behavior, as well as a rich structure of dynamics that includes many ideas from a typical undergraduate dynamical systems course, and some from beyond. Gaining an understanding of the solutions to this model is arguably most easily conducted via a bifurcation analysis of corresponding ODE problems within the software XPPAUT. In this paper, we provide an introductory XPPAUT tutorial, through which we begin to expose the range of intricate patterns that the Gray--Scott model emits.
Citation: SIAM Review
PubDate: 2022-08-04T07:00:00Z
DOI: 10.1137/21M1402868
Issue No: Vol. 64, No. 3 (2022)
-
- Book Reviews
-
Free pre-print version: Loading...
Authors: Volker H. Schulz
Pages: 751 - 759
Abstract: SIAM Review, Volume 64, Issue 3, Page 751-759, August 2022.
The section starts with two hot topics combined into one book: data-driven science and COVID-19. In our featured review, Anita Layton reviews the book Computational Epidemiology: Data-Driven Modeling of COVID-19, by Ellen Kuhl. She concludes her detailed review with the assessment: “This is a timely and truly wonderful book.” Dynamics continues in the second review. The book An Introduction to Nonautonomous Dynamical Systems and Their Attractors, by Peter E. Kloeden and Meihua Yang, is reviewed by Felix Ye, who recommends this book as much more accessible than others. Mathematical fundamentals in a modern guise are presented in A. J. Roberts's book Linear Algebra for the 21st Century. In his review of the book, Joakim Sundnes emphasizes the very contemporary examples it contains. In the subsequent review of the book Numerical Methods for Conservation Laws: From Analysis to Algorithms, by Jan Hesthaven, Jing-Mei Qiu describes it as a future “classic reference book on the computational fluid dynamics shelf.” Afterwards, A. H. Dooley reviews the book Ergodic Dynamics: From Basic Theory to Applications, by Jane Hawkins, and praises it as an introduction to modern ergodic theory and dynamical systems. The section is concluded by my review of Tomé Almeida Borges and Rui Neves's compact book Financial Data Resampling for Machine Learning Based Trading---Application to Cryptocurrency Markets.
Citation: SIAM Review
PubDate: 2022-08-04T07:00:00Z
DOI: 10.1137/22N975548
Issue No: Vol. 64, No. 3 (2022)
-
