R. W. Freund and F. Jarre, A Sensitivity Analysis and a Convergence Result for a Sequential Semidefinite Programming Method
We consider the solution of nonlinear programs with nonlinear semidefiniteness constraints. The need for an efficient exploitation of the cone of positive semidefinite matrices makes the solution of such nonlinear semidefinite programs more complicated than the solution of standard nonlinear programs. In particular, a suitable symmetrization procedure needs to be chosen. The choice of the symmetrization procedure can be shifted in a very natural way to certain linear semidefinite subproblems, and can thus be reduced to a well-studied problem. The resulting sequential semidefinite programming (SSP) method is a generalization of the well-known SQP method for standard nonlinear programs. We present a sensitivity result for nonlinear semidefinite programs, and then use this result to derive an elementary and self-contained proof of local quadratic convergence of the SSP method.
R. W. Freund and F. Jarre, A Sensitivity Result for Semidefinite Programs
We study the sensitivity of unique and strictly complementary solutions of linear semidefinite programs when the data is subject to small arbitrary changes. We present an elementary and self-contained proof of the differentiability of the perturbations of the solutions as functions of the perturbations of the data, and we characterize the derivative as the solution of a system of linear equations. Such a differentiability result was obtained earlier by Shapiro in a more general setting and with a different characterization of the derivative, namely as the solution of a quadratic program. Our result improves upon earlier results that were established by Robinson for more general cone programs. We also present some examples that illustrate why our result does not apply to these more general cone programs.
R. W. Freund, Model Reduction Methods Based on Krylov Subspaces
In recent years, reduced-order modeling techniques based on Krylov-subspace iterations, especially the Lanczos algorithm and the Arnoldi process, have become popular tools for tackling the large-scale time-invariant linear dynamical systems that arise in the simulation of electronic circuits. This paper reviews the main ideas of reduced-order modeling techniques based on Krylov subspaces and describes some applications of reduced-order modeling in circuit simulation.
R. W. Freund, Optimal Pump Control of Broadband Raman Amplifiers via Linear Programming
An algorithm for controlling the pump powers of broadband Raman amplifiers is proposed. The algorithm is based on a variant of the standard Raman model for pump-channel interactions, and determines pump settings that minimize peak-to-peak ripple of the channel powers with respect to any given per-channel target. It is shown that such optimal pump settings can be computed via the solution of linear programs. Some examples are presented.
R. W. Freund, Simulation of Raman Amplification
We present a general formulation of the system of differential equations that describe the power evolution in Raman fiber amplifiers. The solutions of these equations model the forward and backward power spectral densities of Raman amplifiers as functions of position along the fiber, time, and frequency. The time dependence of these equations allows the use of them for simulation of transient effects. The frequency dependence allows the use of these equations for a fully-coupled signal and noise analysis, both in the steady-state and the time-dependent case. The equations include terms that model stimulated Raman scattering, spontaneous Raman scattering due to both Stokes and anti-Stokes emission and absorption, and Rayleigh scattering. We also outline a Galerkin approach for the frequency discretization of the equations.
T. K. Ho, L. C. Cowsar, R. W. Freund, L. Vardapetyan, and T. R. Salamon, Modeling and Simulation of Control Dynamics in Optical Transport Systems
We describe a simulator for modeling complex control dynamics in optical line systems involving the interaction of multiple transmission, control, and monitoring elements in response to channel changes, component failure, and recovery events.
Z. Bai, P. M. Dewilde, and R. W. Freund, Reduced-Order Modeling
In recent years, reduced-order modeling techniques have proven to be powerful tools for various problems in circuit simulation. For example, today, reduction techniques are routinely used to replace the large RCL subcircuits that model the interconnect or the pin package of VLSI circuits by models of much smaller dimension. In this paper, we review the reduced-order modeling techniques that are most widely employed in VLSI circuit simulation.
R. W. Freund and F. Jarre, An Extension of the Positive Real Lemma to Descriptor Systems
The well-known positive real lemma characterizes positive realness of transfer functions of time-invariant linear systems via the solvability of certain linear matrix inequalities. In this paper, we propose an extension of the positive real lemma and the underlying linear matrix inequalities to descriptor systems. We show that the solvability of these linear matrix inequalities is sufficient and, under an additional assumption, also necessary for positive realness of the transfer function of time-invariant linear descriptor systems. We also study a second system of linear matrix inequalities based on a generalized Lyapunov equation. We show that the solvability of this second system is sufficient, but in general not necessary for positive realness.
Z. Bai and R. W. Freund, A Symmetric Band Lanczos Process Based on Coupled Recurrences and Some Applications
The symmetric band Lanczos process is an extension of the classical Lanczos algorithm for symmetric matrices and single starting vectors to multiple starting vectors. After n iterations, the symmetric band Lanczos process has generated an n x n projection, T_n^s, of the given symmetric matrix onto the n-dimensional subspace spanned by the first n Lanczos vectors. This subspace is closely related to the n-th block Krylov subspace induced by the given symmetric matrix and the given block of multiple starting vectors. The standard algorithm produces the entries of T_n^s directly. In this paper, we propose a variant of the symmetric band Lanczos process that employs coupled recurrences to generate the factors of an LDL^T factorization of a closely related n x n projection, rather than T_n^s. This is done in such a way that the factors of the LDL^T factorization inherit the ``fish-bone'' structure of T_n^s. Numerical examples from reduced-order modeling of large electronic circuits and algebraic eigenvalue problems demonstrate that the proposed variant of the band Lanczos process based on coupled recurrences is more robust and accurate than the standard algorithm.
R. W. Freund, Passive Reduced-Order Modeling via Krylov-Subspace Methods
In recent years, Krylov-subspace methods have become popular tools for computing reduced-order models of large-scale time-invariant linear dynamical systems. These techniques produce in a Pade sense optimal reduced-order models. However, when applied to passive systems, the Pade models do not preserve passivity in general. In this paper, we describe a Krylov-subspace technique that generates passive reduced-order models. Results of numerical experiments with a passive system arising in VLSI circuit simulation are reported.
R. W. Freund, Computation of Matrix-Valued Formally Orthogonal Polynomials and Applications
We present a computational procedure for generating formally orthogonal polynomials associated with a given bilinear Hankel form with rectangular matrix-valued moments. Our approach covers the most general case of moments of any size and is not restricted to square moments. Moreover, our algorithm has a built-in deflation procedure to handle linearly dependent or almost linearly dependent columns and rows of the block Hankel matrix associated with the bilinear form. Possible singular or close-to-singular leading principal submatrices of the deflated block Hankel matrix are avoided by means of look-ahead techniques. Applications of the computational procedure to eigenvalue computations, reduced-order modeling, the solution of multiple linear systems, and the fast solution of block Hankel systems are also briefly described.
Z. Bai and R. W. Freund, A Partial Pade-Via-Lanczos Method for Reduced-Order Modeling
The classical Lanczos process can be used to efficiently generate Pade approximants of the transfer function of a given single-input single-output time-invariant linear dynamical system. Unfortunately, in general, the resulting reduced-order models based on Pade approximation do not preserve the stability, and possibly passivity, of the original linear dynamical system. In this paper, we describe the use of partial Pade approximation for reduced-order modeling. Partial Pade approximants have a number of prescribed poles and zeros, while the remaining degrees of freedom are used to match the Taylor expansion of the original transfer function in as many leading coefficients as possible. We present an algorithm for computing partial Pade approximants via suitable rank-1 updates of the tridiagonal matrices generated by the Lanczos process. Numerical results for two circuit examples are reported.
R. W. Freund, Krylov-Subspace Methods for Reduced-Order Modeling in Circuit Simulation
The simulation of electronic circuits involves the numerical solution of very large-scale, sparse, in general nonlinear, systems of differential-algebraic equations. Often, the size of these systems can be reduced considerably by replacing the equations corresponding to linear subcircuits by approximate models of much smaller state-space dimension. In this paper, we describe the use of Krylov-subspace methods for generating such reduced-order models of linear subcircuits. Particular emphasis is on reduced-order modeling techniques that preserve the passivity of linear RLC subcircuits.
R. W. Freund and F. Jarre, Solving the Sum-of-Ratios Problem by an Interior-Point Method
We consider the problem of minimizing the sum of a convex function and of $p\ge 1$ fractions subject to convex constraints. The numerators of the fractions are positive convex functions, and the denominators are positive concave functions. Thus, each fraction is quasi-convex. We give a brief discussion of the problem and prove that in spite of its special structure, the problem is ${\cal NP}$-complete even when only $p=1$ fraction is involved. We then show how the problem can be reduced to the minimization of a function of $p$ variables where the function values are given by the solution of certain convex subproblems. Based on this reduction, we propose an algorithm for computing the global minimum of the problem by means of an interior-point method for convex programs.
D. J. Estep and R. W. Freund, Using Krylov-Subspace Iterations in Discontinuous Galerkin Methods
We consider discontinuous in time and continuous in space Galerkin finite-element methods for the numerical solution of reaction-diffusion differential equations. These are implicit methods that require the solution of a system of nonlinear equations at each time node. In this paper, we explore the use of Krylov-subspace techniques for the iterative solution of the linear systems that arise when these nonlinear systems are solved by means of Newton-type methods. It is shown how these linear systems depend on the choice of the basis functions used for the time discretization. We demonstrate that Krylov-subspace methods can be sped up considerably by employing an orthogonal basis for the time discretization and by combining the Krylov iteration with a suitable block preconditioner. Results of numerical experiments are reported.
Z. Bai and R. W. Freund, Eigenvalue-Based Characterization and Test for Positive Realness of Scalar Transfer Functions
An eigenvalue-based characterization of positive realness of transfer functions of single-input single-output time-invariant linear systems is derived. Based on this characterization, we propose efficient computational procedures to determine if a given transfer function is positive real. The input for these eigenvalue-based tests is any given, not necessarily minimal, state-space representation of the linear system. Furthermore, the tests only involve standard matrix computations, such as computing eigenvalues of a matrix or a matrix pencil. Results of numerical experiments with these eigenvalue-based tests for positive realness are reported.
R. W. Freund, Templates for Band Lanczos Methods and for the Complex Symmetric Lanczos Method
The classical Lanczos process is a powerful tool for various computations involving large square matrices. The band Lanczos method is an extension of the classical Lanczos process for a pair of single starting vectors, to blocks of starting vectors. The method generates bi-orthogonal basis vectors for the right and left block-Krylov subspaces induced by the right and left starting blocks and the given square matrix, as well as an oblique projection of the given matrix onto the right block-Krylov subspace and orthogonal to the left block-Krylov subspace. In this paper, we present algorithmic descriptions of the Hermitian band Lanczos method, of the non-Hermitian band Lanczos method, and of a variant of the Lanczos process tailored to complex symmetric matrices. (The three sections of this paper are invited sections for the book project Templates for the Solution of Algebraic Eigenvalue Problems: a Practical Guide .)
R. W. Freund, Passive Reduced-Order Models for Interconnect Simulation and Their Computation via Krylov-Subspace Algorithms
This paper studies a general projection technique based on block Krylov subspaces for the computation of reduced-order models of multi-port RLC circuits. We show that the resulting reduced-order models are always passive, yet they still match at least half as many moments as the corresponding reduced-order models based on matrix-Pade approximation. Moreover, for the special cases of RC, RL, and LC circuits, the reduced-order models obtained by projection and by matrix-Pade approximation are identical. For general RLC circuits, we show how the projection technique can easily be incorporated into the SyMPVL algorithm to obtain passive reduced-order models, in addition to the high-accuracy matrix-Pade approximation that characterizes SyMPVL, at essentially no extra computational costs. Connections between SyMPVL and the recently proposed reduced-order modeling algorithm PRIMA are also discussed. Numerical results for interconnect simulation problems are reported.
J. I. Aliaga, D. L. Boley, R. W. Freund, and V. Hernandez, A Lanczos-Type Method for Multiple Starting Vectors
Given a square matrix and single right and left starting vectors, the classical nonsymmetric Lanczos process generates two sequences of biorthogonal basis vectors for the right and left Krylov subspaces induced by the given matrix and vectors. In this paper, we propose a Lanczos-type algorithm that extends the classical Lanczos process for single starting vectors to multiple starting vectors. Given a square matrix and two blocks of right and left starting vectors, the algorithm generates two sequences of biorthogonal basis vectors for the right and left block Krylov subspaces induced by the given data. The algorithm can handle the most general case of right and left starting blocks of arbitrary sizes, while all previously proposed extensions of the Lanczos process are restricted to right and left starting blocks of identical sizes. Other features of our algorithm include a built-in deflation procedure to detect and delete linearly dependent vectors in the block Krylov sequences, and the option to employ look-ahead to remedy the potential breakdowns that may occur in nonsymmetric Lanczos-type methods. (This is a substantially revised version of the Numerical Analysis Manuscript 96/4-18.ps.)
R. W. Freund, Reduced-Order Modeling Techniques Based on Krylov Subspaces and Their Use in Circuit Simulation
In recent years, reduced-order modeling techniques based on Krylov-subspace iterations, especially the Lanczos algorithm and the Arnoldi process, have become popular tools to tackle the large-scale time-invariant linear dynamical systems that arise in the simulation of electronic circuits. This paper reviews the main ideas of reduced-order modeling techniques based on Krylov subspaces and describes the use of reduced-order modeling in circuit simulation.
Z. Bai, P. Feldmann, and R. W. Freund, How to Make Theoretically Passive Reduced-Order Models Passive in Practice
This paper demonstrates that, in general, implementations of circuit reduction methods can produce unstable and non-passive models even when such outcomes are theoretically proven to be impossible. The reason for this apparent contradiction is the numeric roundoff inherent in any finite-precision computer implementation. This paper introduces a new variant of the symmetric, multi-port, Pade via Lanczos algorithm (SyMPVL) that, even in practice, is guaranteed to produce stable and passive models for all the circuits characterized by pairs of symmetric, positive semidefinite matrices. The algorithm is based by a new band Lanczos process with coupled recurrences. A number of circuit examples are used to illustrate the results.
R. W. Freund, F. Jarre, and S. Mizuno, Convergence of a Class of Inexact Interior-Point Algorithms for Linear Programs
We present a convergence analysis for a class of inexact infeasible-interior-point methods for solving linear programs. The main feature of inexact methods is that the linear systems defining the search direction at each interior-point iteration need not be solved to high accuracy. More precisely, we allow that these linear systems are only solved to a moderate accuracy in the residual, but no assumptions are made on the accuracy of the search direction in the search space. In particular, our analysis does not require that feasibility is maintained even if the initial iterate happened to be a feasible solution of the linear program. We also present a few numerical examples to illustrate the effect of using inexact search direction on the number of interior-point iterations. (This is a revised version of the Numerical Analysis Manuscript 96/4-16.ps.)
Z. Bai, P. Feldmann, and R. W. Freund, Stable and Passive Reduced-Order Models Based on Partial Pade Approximation Via the Lanczos Process
This paper describes the use of partial Pade approximation to generate stable and passive reduced-order models of linear circuits. For similarly-sized models, partial Pade-based reduced-oreder modeling has superior moment-matching capabilities than competing techniques based on the Arnoldi process. The paper introduces PVL$\pi$, an algorithm for computing partial Pade-based reduced-order models via the Lanczos process. The effectiveness of this modeling methodology is illustrated by numerical examples.
R. W. Freund, Computing Minimal Partial Realizations Via a Lanczos-Type Algorithm for Multiple Starting Vectors
We describe a Lanczos-type procedure that reduces a given realization of a finite sequence of (moment) matrices to a minimal partial realization. A key feature of this procedure is that the underlying Lanczos-type algorithm is directly applied to the matrix triplet describing the given realization, rather than to the moment matrices. It thus avoids explicit formulation of and the usually unstable computation with the moment matrices.
W. M. Coughran, Jr. and R. W. Freund, Recent Advances in Krylov-Subspace Solvers for Linear Systems and Applications in Device Simulation
The computational cost of many simulations is dominated by the solution of large, sparse systems of linear equations. Krylov-subspace methods, especially when combined with suitable preconditioning, are powerful algorithms for the iterative solution of such linear systems. One of the features of Krylov-subspace methods is that the matrix of the linear system is only used in the form of matrix-vector products, and thus sparsity is naturally exploited. In recent years, there have been many advances in Krylov-subspace methods for the solution of large, sparse, nonsymmetric linear systems. In this paper, we survey some of these recent advances, especially in the area of Lanczos-based methods. We also discuss the use of state-of-the-art Krylov-subspace methods in device simulation.
R. W. Freund and P. Feldmann, The SyMPVL Algorithm and Its Applications to Interconnect Simulation
This paper describes SyMPVL, an algorithm for the computation of multi-port transfer functions of RLC circuits. SyMPVL employs a J-symmetric Lanczos-type algorithm for multiple starting vectors to reduce the original circuit matrices to a pair of banded symmetric matrices. These matrices, which are typically much smaller than the circuit matrices, determine a reduced-order model of the original multi-port. The transfer function of the model represents a matrix-Pade approximation of the multi-port matrix transfer function. Numerical results for SyMPVL applied to interconnect simulation problems are reported.
R. W. Freund, Preconditioning of Symmetric, but Highly Indefinite Linear Systems
Many important applications involve the solution of large linear systems with symmetric, but highly indefinite coefficient matrices with both many positive and many negative eigenvalues. For example, such systems arise in incompressible flow computations and as subproblems in optimization algorithms for linear and nonlinear programs. Often, these systems are very large and sparse, and it then becomes attractive to use a preconditioned iterative method, such as the symmetric QMR algorithm, for their solution. In this paper, we first briefly review the symmetric QMR algorithm, and we then discuss the construction of efficient preconditioners for highly indefinite symmetric linear systems. We report a few results of numerical experiments with symmetric indefinite linear systems arising in linear programming and in fluid-flow computations.
R. W. Freund and M. Malhotra, The Block-QMR Method for the Solution of Multiple Radiation and Scattering Problems in Structural Acoustics
Finite-element discretizations of time-harmonic acoustic wave problems in underwater structural acoustics result in large sparse systems of linear equations with complex symmetric coefficient matrices. Often, these matrix problems need to be solved repeatedly for different right-hand sides, but with the same matrix. We discuss the use of the block-QMR method for the iterative solution of these multiple linear systems.
P. Fiebach, R. W. Freund, and A. Frommer, Variants of the Block-QMR Method and Applications in Quantum Chromodynamics
Numerical computations in lattice quantum chromodynamics (QCD) require the solution of large sparse systems of linear equations. These systems are so large that they can only be tackled by iterative solution techniques. In certain QCD simulations, a sequence of closely related linear systems has to be solved. In a quenched simulation, all systems have the same coefficient matrix, but differ in their right-hand sides. In the multiboson framework, systems with coefficient matrices that differ only by an additive shift have to be solved. In this paper, we describe variants of the block-QMR method that are tailored to these two classes of multiple linear systems. Numerical results with linear systems from QCD simulations are reported.
P. Feldmann and R. W. Freund, Circuit Noise Evaluation by Pade Approximation Based Model-Reduction Techniques
This paper introduces a new circuit noise analysis and modeling method. The noise analysis method computes an analytic expression of frequency, in rational form, which represents the Pade approximation of the power spectral density of noise. The approximation can be carried out efficiently, to any desired level of accuracy using a variant of the PVL or MPVL algorithms. The new method is significantly more efficient than traditional methods for noise computation at numerous frequency points. In addition, it allows for a compact and cascadable modeling of noise that can be used in system level simulations.
P. Feldmann and R. W. Freund, Interconnect-Delay Computation and Signal-Integrity Verification Using the SyMPVL Algorithm
This paper describes a methodology for interconnect-delay estimation, modeling, and signal-integrity verification. The methodology relies on a recently introduced powerful algorithm, SyMPVL (Symmetric Matrix-Pad\'e via Lanczos). SyMPVL is an efficient and numerically stable algorithm for the computation of matrix-Pad\'e approximations for large, linear, passive network transfer functions. The approximated transfer function is used to compute signal waveforms with sufficient accuracy to estimate delay and verify against signal-integrity violations. It can also serve as a compact model of the interconnect network.
R. W. Freund and P. Feldmann, Reduced-Order Modeling of Large Linear Passive Multi-terminal Circuits Using Matrix-Pade Approximation
This paper introduces SyMPVL, an algorithm for the computation of the symmetric multi-port transfer function of an RLC circuit. The algorithm employs a novel symmetric block-Lanczos algorithm to reduce the original circuit matrices to a pair of banded symmetric matrices. These matrices, which are typically much smaller than the circuit matrices, determine a reduced-order model of the original multi-port. The transfer function of the model represents a matrix-Pad\'e approximation of the multi-port matrix transfer function. In this paper, we describe the symmetric formulation of RLC multi-port transfer functions, present the symmetric block-Lanczos algorithm, prove stability and passivity of the reduced-order models in the RL, RC, and LC special cases, and report numerical results for SyMPVL applied to example circuits.
A. Benvenuti, W. M. Coughran, Jr., and M. R. Pinto A Thermal-Fully Hydrodynamic Model for Semiconductor Devices and Applications to III-V HBT Simulation
Because of the interaction between thermal and hot carriers effects, neither isothermal nor conventional macro\-thermal models are adequate for the simulation of state-of-the-art III-V power devices; instead, a non-isothermal hot carrier transport model, such as the thermal-fully hydrodynamic model, is required. We apply a 1D implementation of such a detailed thermal model to the simulation of AlGaAs/GaAs and InP/InGaAs heterojunction bipolar transistors, comparing the results with those provided by simplified models, and highlighting how deeply both non-stationary transport and self-heating affect the predicted device performance. The importance of the convective terms is assessed, and a new non-thermal mechanism for the output negative differential resistance is proposed.
Freund, R. W., Circuit Simulation Techniques Based on Lanczos-Type Algorithms
Circuit simulation tasks often require the numerical analysis of large linear networks. These networks can become extremely large, and then the use of time-domain differential equation integration as implemented in SPICE-like circuit simulators, would be inefficient or even prohibitive. A much more efficient approach is to generate reduced-order models of the large networks, based on approximations to the frequency-domain transfer function of the network. This paper describes the computation of Pad\'e-based reduced-order models of large linear networks via Lanczos-type algorithms.
Aliaga, J. I., Boley, D. L., Freund, R. W., and Hernandez, V., A Lanczos-Type Method for Multiple Starting Vectors
Given a square matrix and single right and left starting vectors, the classical nonsymmetric Lanczos process generates two sequences of biorthogonal basis vectors for the right and left Krylov subspaces induced by the given matrix and vectors. In this paper, we propose a Lanczos-type algorithm that extends the classical Lanczos process for single starting vectors to multiple starting vectors. Given a square matrix and two blocks of right and left starting vectors, our algorithm generates two sequences of biorthogonal basis vectors for the right and left block Krylov subspaces induced by the given data. The algorithm can handle the most general case of right and left block Krylov subspaces with arbitrary sizes of the starting blocks, while all previously proposed extensions of the Lanczos process are restricted to right and left starting blocks of identical sizes. Other features of our algorithm include a built-in deflation procedure to detect and delete linearly dependent or almost linearly dependent vectors in the block Krylov sequences, and the option to employ look-ahead in order to avoid the potential breakdowns that are typical for nonsymmetric Lanczos-type methods.
Freund, R. W., Jarre. F., and Mizuno, S., Convergence of a Class of Inexact Interior-Point Algorithms for Linear Programs
We present a convergence analysis for a class of inexact infeasible-interior-point methods for solving linear programs. The main feature of inexact methods is that the linear systems defining the search direction at each interior-point iteration need not be solved to high accuracy. More precisely, we allow that these linear systems are only solved to a moderate relative accuracy in the {\em residual\/}, but no assumptions are made on the accuracy of the search direction in the search space. In particular, our analysis does not require that feasibility is maintained even if the initial iterate happened to be a feasible solution of the linear program.
Freund, R. W. and Feldmann, P., Reduced-Order Modeling of Large Passive Linear Circuits by Means of the SyPVL Algorithm
This paper discusses the analysis of large linear electrical networks consisting of passive components, resistors, capacitors, inductors, transformers, etc. Such networks result in a symmetric formulation of circuit equations. The paper introduces SyPVL, an efficient and numerically stable algorithm for the computation of reduced-order models of large, linear, passive networks. SyPVL represents the specialization of the more general PVL algorithm, to symmetric problems. Besides the gain in efficiency over PVL, SyPVL also preserves the symmetry of the problem, and, as a consequence, can often guarantee the stability of the resulting reduced-order models. Moreover, the resulting reduced-order models can be synthesized as actual physical circuits, thus facilitating compatibility with existing analysis tools. The application of SyPVL is illustrated in the paper with a few interconnect analysis examples.
Malhotra, M., Freund, R. W., and Pinsky, P. M., Iterative solution of multiple radiation and scattering problems in structural acoustics using a block quasi-minimal residual algorithm
Finite-element discretizations of time-harmonic acoustic wave problems in exterior domains result in large sparse systems of linear equations with complex symmetric coefficient matrices. In many situations, these matrix problems need to be solved repeatedly for different right-hand sides, but with the same coefficient matrix. Recently, Freund and Malhotra have proposed a block quasi-minimal residual (BL-QMR) algorithm for the iterative solution of non-Hermitian linear systems with multiple right-hand sides. The BL-QMR algorithm is a block Krylov-subspace iterative method that incorporates deflation to delete linearly and almost linearly dependent vectors in the underlying block Krylov sequences. In this paper, we describe a J-symmetric variant of the BL-QMR algorithm that introduces important simplifications for the case when the coefficient matrix is symmetric with respect to a bilinear form induced by a certain matrix J. In particular, the J-symmetric variant includes the complex symmetric form of BL-QMR as a special case. We identify suitable preconditioners for the BL-QMR algorithm applied to multiple radiation and scattering problems. Our numerical tests with the preconditioned BL-QMR algorithm for such multiple linear systems show that, instead of solving each of the linear systems individually, it is significantly more efficient to employ the block version of the iterative method. Moreover, the numerical results clearly illustrate the importance of deflation and its effect on iterative convergence.
Freund, R. W. and Malhotra, M., A Block-QMR Algorithm for Non-Hermitian Linear Systems with Multiple Right-Hand Sides
Many applications require the solution of multiple linear systems that have the same coefficient matrix, but differ in their right-hand sides. Instead of applying an iterative method to each of these systems individually, it is more efficient to employ a block version of the method that generates iterates for all the systems simultaneously. In this paper, we propose a block version of Freund and Nachtigal's quasi-minimal residual (QMR) method for the iterative solution of non-Hermitian linear systems. The block-QMR method uses a novel Lanczos-type process for multiple starting vectors, which was recently developed by Aliaga, Boley, Freund, and Hernandez, to compute suitable basis vectors for the underlying block Krylov subspaces. We describe the basic block-QMR method, and also give important implementation details. In particular, we show how to incorporate deflation to drop converged linear systems, and to delete linearly and almost linearly dependent vectors in the underlying block Krylov sequences. Numerical results are reported that illustrate typical features of the block-QMR method.
Freund, R. W. and Feldmann, P., Small-Signal Circuit Analysis and Sensitivity Computations with the PVL Algorithm IEEE Transactions on Circuits and and Systems-II: Analog and Digital Signal Processing, to appear
We describe the application of the PVL algorithm to the small-signal analysis of circuits, including sensitivity computations. The PVL algorithm is based on the efficient computation of the Pade approximation of the network transfer function via the Lanczos process. The numerical stability of the algorithm permits the computation of the Pade approximation to any accuracy over a certain frequency range. We extend the algorithm to compute sensitivities of network transfer functions, their poles, and their zeros, with respect to arbitrary circuit parameters, with minimal additional computational cost. We demonstrate the implementation of our algorithm on circuit examples.
Freund, R. W., Computation of Matrix Pade Approximations of Transfer Functions Via a Lanczos-Type Process Approximation Theory VIII, Vol.1: Approximation and Interpolation, (C. K. Chui and L. L. Schumaker, eds.), World Scientific Publishing Co., 1995
We present an approach for the stable and efficient computation of matrix Pade approximations of transfer functions of general multi-input multi-output linear dynamical systems. The proposed method is based on a recently developed Lanczos-type process for multiple starting vectors. We establish a connection between this Lanczos process and matrix Pade approximants of transfer functions.
Freund, R. W. and Nachtigal, N. M., Software for Simplified Lanczos and QMR Algorithms Applied Numerical Mathematics, Vol. 19, 1995
The nonsymmetric Lanczos process simplifies when applied to J-symmetric and J-Hermitian matrices, and work and storage requirements are roughly halved compared to the general case. In this paper, we describe FORTRAN-77 implementations of simplified versions of the look-ahead Lanczos algorithm and of the quasi-minimal residual (QMR) method, which is a Lanczos-based iterative procedure for the solution of linear systems. These implementations of the simplified algorithms complete our software package QMRPACK, which so far contained only codes for Lanczos and QMR algorithms for general matrices. We describe in some detail the use of two routines, one for the solution of linear systems, and the other for eigenvalue computations. We present examples that lead to J-symmetric and J-Hermitian matrices. Results of numerical experiments are reported.
Freund, R. W. and Jarre, F., A QMR-Based Interior-Point Algorithm for Solving Linear Programs Math. Programming, Ser. B, to appear
A new approach for the implementation of interior-point methods for solving linear programs is proposed. Its main feature is the iterative solution of the symmetric, but highly indefinite 2x2-block systems of linear equations that arise within the interior-point algorithm. These linear systems are solved by a symmetric variant of the quasi-minimal residual (QMR) algorithm, which is an iterative solver for general linear systems. The symmetric QMR algorithm can be combined with indefinite preconditioners, which is crucial for the efficient solution of highly indefinite linear systems, yet it still fully exploits the symmetry of the linear systems to be solved. To support the use of the symmetric QMR iteration, a novel stable reduction of the original unsymmetric 3x3-block systems to symmetric 2x2-block systems is introduced, and a measure for a low relative accuracy for the solution of these linear systems within the interior-point algorithm is proposed. Some indefinite preconditioners are discussed. Finally, we report results of a few preliminary numerical experiments to illustrate the features of the new approach.
Freund, R. W., Jarre, F., and Schaible, S., On Interior-Point Methods for Fractional Programs and Their Convex Reformulation A short version of this paper will appear in Math. Programming
We consider the problem of minimizing a convex-concave fraction subject to convex constraints, using interior-point methods. The problem can be solved by applying an interior-point method directly to the original nonconvex problem, or by applying an interior-point method to an equivalent convex reformulation of the original problem. In this paper, these two approaches are compared, and it is shown that the rate of convergence is of the same order in both cases. As our main result, we determine the optimal coefficients in the construction of a self-concordant barrier function for the convex reformulation of the original problem.
Freund, R. W. and Nachtigal, N. M., QMRPACK: a Package of QMR Algorithms ACM Transactions on Mathematical Software, to appear
The quasi-minimal residual (QMR) algorithm is a Krylov-subspace method for the iterative solution of large non-Hermitian linear systems. QMR is based on the look-ahead Lanczos algorithm that, by itself, can also be used to obtain approximate eigenvalues of large non-Hermitian matrices. QMRPACK is a software package with FORTRAN-77 implementations of the QMR algorithm and variants thereof, and of the three-term and coupled two-term look-ahead Lanczos algorithms. In this paper, we discuss some of the features of the algorithms in the package, with emphasis on the issues related to using the codes. We describe in some detail two routines from the package, one for the solution of linear systems, and the other for the computation of eigenvalue approximations. We present some numerical examples from applications where QMRPACK was used.
Shirley Browne, Jack Dongarra, Eric Grosse, Stan Green, Keith Moore, Tom Rowan, and Reed Wade Netlib Services and Resources
The Netlib repository contains freely available software, documents, and databases of interest to the numerical, scientific computing, and other communities. The repository is maintained by AT&T Bell Laboratories, the University of Tennessee and Oak Ridge National Laboratory, and by colleagues world-wide. This report includes both the Netlib User's Guide and the Netlib System Manager's Guide, and contains information about Netlib's databases, interfaces, and system implementation. The Netlib repository's databases include the Performance Database, the Conferences Database, and numerous bibliographic and address databases. A variety of user interfaces enable users to access the Netlib repository in the manner most convenient and compatible with their networking capabilities.
Available in HTML form.
Feldmann, P. and Freund, R. W., Reduced-Order Modeling of Large Linear Subcircuits via a Block Lanczos Algorithm Proceedings of the 32nd Design Automation Conference, 1995
In this paper, we describe a method for the efficient computation of accurate reduced-order models of large linear circuits. The method, called MPVL, represents a generalization of the previously published PVL algorithm, and employs a novel block Lanczos algorithm to compute matrix Pade approximations of matrix-valued network transfer functions. The reduced-order models, computed to the required level of accuracy, are used to speed up the analysis of circuits containing large linear blocks. The linear blocks are replaced by their reduced-order models, and the resulting, smaller, circuit can be analyzed with general purpose simulators, such as SPICE, with significant savings in simulation time and, practically, no loss of accuracy.
Baldwin, C., Freund, R. W., and Gallopoulos, E., A Parallel Iterative Method for Exponential Propagation Proceedings of the Seventh SIAM Conference on Parallel Processing for Scientific Computing, 1995
We consider the computation of x := exp(-A) b, where b is a vector and A is a matrix of order N, possibly nonsymmetric, by means of iterative methods. The algorithm is based on a transpose-free quasi-minimal residual algorithm to efficiently compute the solution of systems (A - z_j I) x_j = b for several distinct values of the shift z_j, and on the partial-fraction representation of rational approximations of the matrix exponential. We outline mappings of the algorithm on a parallel architecture, present numerical experiments, and discuss the computational performance of the algorithm.
Freund, R. W. and Feldmann, P., Efficient Small-Signal Circuit Analysis and Sensitivity Computations with the PVL Algorithm Technical Digest of the 1994 IEEE/ACM International Conference on Computer-Aided Design
In this paper we describe the application of the PVL algorithm to the small-signal analysis of circuits, including sensitivity computations. The PVL algorithm is based on the efficient computation of the Pade approximation of the network transfer function via the Lanczos process. The numerical stability of the algorithm permits the computation of the Pade approximation to any accuracy over a certain frequency range. We extend the algorithm to compute sensitivities of network transfer functions, their poles, and zeros, with respect to arbitrary circuit parameters, with minimal additional computational cost. We then demonstrate the implementation of our algorithm on circuit examples.
Freund, R. W. and Nachtigal, N. M., QMRPACK and Applications Proceedings of the 14th IMACS World Congress, to appear
QMRPACK is a package of quasi-minimal residual algorithms for the iterative solution of linear systems. In this paper, we describe the main features of QMRPACK, comment on the implementations found in the package, and discuss how they would be invoked in a user code. We briefly describe two applications of the codes in the area of simulation of material properties from first principles, and in circuit simulation. We conclude by presenting future directions for QMRPACK.
Freund, R. W. and Nachtigal, N. M., A New Krylov-Subspace Method for Symmetric Indefinite Linear Systems Proceedings of the 14th IMACS World Congress, 1994
Many important applications involve the solution of large linear systems with symmetric, but indefinite coefficient matrices. For example, such systems arise in incompressible flow computations and as subproblems in optimization algorithms for linear and nonlinear programs. Existing Krylov-subspace iterations for symmetric indefinite systems, such as SYMMLQ and MINRES, require the use of symmetric positive definite preconditioners, which is a rather unnatural restriction when the matrix itself is highly indefinite with both many positive and many negative eigenvalues. In this note, we describe a new Krylov-subspace iteration for solving symmetric indefinite linear systems that can be combined with arbitrary symmetric preconditioners. The algorithm can be interpreted as a special case of the quasi-minimal residual method for general non-Hermitian linear systems, and like the latter, it produces iterates defined by a quasi-minimal residual property. The proposed method has the same work and storage requirements per iteration as SYMMLQ or MINRES, however, it usually converges in considerably fewer iterations. Results of numerical experiments are reported.
Freund, R. W., The Look-Ahead Lanczos Process for Nonsymmetric Matrices and its Applications Proceedings of the Lanczos Centenary Conference, 1994
The nonsymmetric Lanczos process can be used to compute approximate eigenvalues of large non-Hermitian matrices and to obtain approximate solutions of large non-Hermitian linear systems. However, the Lanczos algorithm in its original form is susceptible to possible breakdowns and potential instabilities. We describe a look-ahead variant of the Lanczos process that remedies the problems of the original algorithm, and we discuss some of its applications. We also describe related algorithms for constructing formally orthogonal polynomials and for computing inverse triangular factorizations of Hankel matrices.
Freund, R. W., Lanczos-Type Algorithms for Structured Non-Hermitian Eigenvalue Problems Proceedings of the Lanczos Centenary Conference, 1994
The nonsymmetric Lanczos process is a powerful tool for computing a few eigenvalues of large non-Hermitian matrices. Many important applications lead to non-Hermitian matrices that exhibit special structures, such as Hamiltonian or Toeplitz matrices. In this note, we describe variants of the Lanczos process that exploit such special structures.
Fischer, B. and Freund, R. W., An Inner Product-Free Conjugate Gradient-Like Algorithm for Hermitian Positive Definite Systems Proceedings of the Lanczos Centenary Conference, 1994
The conjugate gradient (CG) algorithm for the solution of Hermitian positive definite linear systems requires the computation of inner products. On modern architectures, inner products often represent a bottleneck, and it is desirable to reduce or even eliminate all the inner products. In this note, an inner product-free CG-like algorithm is presented that simulates the standard CG method by approximating the CG orthogonal polynomials by suitably chosen orthogonal polynomials from the Bernstein-Szegoe class.
Bjorstad, Coughran, Grosse, Parallel Domain Decomposition Applied to Coupled Transport Equations 7th Int. Conf. on Domain Decomposition Methods in Scientific and Engineering Computing (American Mathematical Society)
Modeling semiconductor devices is an important technological problem. The traditional approach solves coupled advection-diffusion carrier-transport equations in two and three spatial dimensions on either high-end scientific workstations or traditional vector supercomputers. The equations need specialized discretizations as well as nonlinear and linear iterative methods. We will describe some of these techniques and our preliminary experience with coarse-grained domain-decomposition techniques applied on a collection of high-performance workstations connected at a 100Mb/s shared network.
Feldmann, P. and Freund, R. W., Efficient Linear Circuit Analysis by Pade Approximation via the Lanczos Process Proceedings of EURO-DAC '94 with EURO-VHDL '94, 1994
This paper describes a highly efficient and numerically stable algorithm for the iterative computation of dominant poles and zeros of large linear networks. The algorithm is based on a new implementation of the Pade approximation via the Lanczos process. This implementation has considerably superior numerical properties, while maintaining the same computational efficiency as its predecessors. In addition, the algorithm provides a bound on the pole approximation error.
Cowsar, Lawrence C., Dupont, Todd F., and Wheeler, Mary F., A priori estimates for mixed finite element approximations of second order hyperbolic equations with absorbing boundary conditions , to appear in SINUM
Optimal order $L^\infty$-in-time, $L^2$-in-space a priori error estimates are derived for mixed finite element approximations for both displacement and stress for a second order hyperbolic equation with first order absorbing boundary conditions. Continuous-in-time, explicit-in-time, and implicit-in-time procedures are formulated and analyzed.
Cowsar, Lawrence C., Some Domain Decomposition and Multigrid Preconditioners for Hybrid Mixed Finite Elements
Eric Grosse and John D. Hobby, Improved Rounding for Spline Coefficients and Knots Mathematics of Computation, 63:207, 175-194
When representing the coefficients and knots of a spline using only small integers, independently rounding each infinite precision value is not the best strategy. We show how to build an affine model for the error expanded about the optimal full-precision free-knot or parameterized spline, then use the Lovasz basis reduction algorithm to select a better rounding. The technique could be used for other situations in which a quadratic error model can be computed.
Pommerell, Claude and Ruehl, Roland, Compiler Assisted Distributed Memory Parallelization of an Iterative Solver for Irregular Sparse Linear Systems
Freund, R. W., A Look-Ahead Bareiss Algorithm for General Toeplitz Matrices
Gay, David M., Hooking Your Solver to AMPL
This report tells how to make solvers work with AMPL's solve command.
Freund, R. W., A Look-Ahead Schur-Type Algorithm for Solving General Toeplitz Systems
Freund, R. W. and Jarre, F., A Polynomial-Time Algorithm for Fractional Programs with Convex Constraints
Freund, R. W. and Jarre, F., An Interior-Point Method for Multi-Fractional Programs with Convex Constraints
Fourer, Robert and Gay, David M., Experience with a Primal Presolve Algorithm
Sometimes an optimization problem can be simplified to a form that is faster to solve. Indeed, sometimes it is convenient to state a problem in a way that admits some obvious simplifications, such as eliminating fixed variables and removing constraints that become redundant after simple bounds on the variables have been updated appropriately. Because of this convenience, the AMPL modeling system includes a ``presolver'' that attempts to simplify a problem before passing it to a solver. The current AMPL presolver carries out all the primal simplifications described by Brearely et al. in 1975. This paper describes AMPL's presolver, discusses reconstruction of dual values for eliminated constraints, and presents some computational results.
Eric Grosse, Approximation in VLSI Simulation Numerical Algorithms, 1993, 5:591-601
Numerical approximation has played a valuable supporting role in VLSI device simulation. Examples include 1) tensor product variation diminishing splines for models of transistor charges and currents and 2) continuation to find a safe operating region avoiding avalanche breakdown. More recently quadratic box splines in three variables have been studied for use in Monte Carlo solution of the Boltzman transport equation. The bivariate Zwart-Powell element does not directly generalize, but another particular box spline is constructed.
Eric Grosse, Repository Mirroring ACM Trans. on Math. Software, accepted
Distributed administration of network repositories demands a low overhead procedure for cooperating repositories around the world to ensure they hold identical contents. {\em Netlib} has adopted some refinements on the widespread scheme of anonymous {\tt ftp} and {\tt ls-lR}. Checksum files and a two small C programs give an easily maintained system that copes with communication breakdowns and subtle changes in repository contents. The packaging of these C programs inside a shell pipeline provides an explicit command stream that can readily be checked before execution. Protecting files, keeping logs, and so forth becomes effortless and reliable. The same tools, applied on a smaller scale, allow more people to participate in the editorial work of maintaining a high-quality repository, by eliminating the need for directly manipulating files at remote sites.
Freund, R. W. and Jarre, F., An Interior-Point Method for Convex Fractional Programming
Wright, Margaret H., Why a pure primal {N}ewton barrier step may be infeasible
Wright, Margaret H., Some Linear Algebra Issues in Large-Scale Optimization
Cowsar, Lawrence C., Mandel, Jan and Wheeler, Mary F., Balancing Domain Decomposition for Mixed Finite Elements, to appear in Math. of Comp.
The rate of convergence of the balancing domain decomposition method applied to the mixed finite element discretization of second order elliptic equations is analyzed. The balancing domain decomposition method, introduced by Mandel, is a substructuring method that involves at each iteration the solution of a local problem with Dirichlet data, a local problem with Neumann data, and a ``coarse-grid'' problem to propagate information globally and to insure the consistency of the Neumann problem. It is shown that the asymptotic condition number grows at worst like the logarithm squared of the ratio of the size of the subdomain to the size of elements are derived in both two and three dimensions and for elements of arbitrary order. The bounds are uniform with respect to coefficient jumps of arbitrary size between subdomains. The key component of our analysis is the demonstration of an equivalence between the norm induced by the bilinear form on the interface and the $H^{1/2}$-norm of an interpolant of the boundary data. Computational examples from a message passing parallel implementation on an INTEL-Delta machine are presented.
Freund, R. W., Solution of Shifted Linear Systems by Quasi-Minimal Residual Iterations
Freund, R. W. and Nachtigal, N. M., Implementation Details of the Coupled {QMR} Algorithm
Freund, Roland W. and Zha, Hongyuan, Formally Biorthogonal Polynomials and a Look-Ahead {L}evinson Algorithm for General {T}oeplitz Systems
Freund, R. W., Transpose-Free Quasi-Minimal Residual Methods for Non-{H}ermitian Linear Systems
Freund, R. W. and Nachtigal, N. M., An Implementation of the {QMR} Method Based on Coupled Two-Term Recurrences
Wright, Margaret H., Determining subspace information from the Hessian of a barrier function
Murray, Walter and Wright, Margaret H., Line Search Procedures for the Logarithmic Barrier Function, to appear in the SIAM Journal on Optimization
Feigenbaum, Grosse, Reeds, Cryptographic Protection of Membership Lists IACR Newsletter, 1992, 9:1, 16-20
We present a simple algorithm for encrypting membership lists. The encrypted lists and search software can be distributed to members of the organization, who can use them to make legitimate queries. However, it is difficult to use the encrypted list for unauthorized purposes, such as the generation of sales lists. We illustrate the method by applying it to the SIAM membership list, yielding a package that can be widely distributed.
Wright, Margaret H., Interior Methods for Constrained Optimization, in Acta Numerica 1992 (A. Iserles, ed.), Cambridge University Press, New York, 341-407.
Coughran and Grosse, Display of Functions of Three Space Variables and Time Using Shaded Polygons and Sound IFIP, Prog Envir for High-Level Sci Problem Solving, Karlsruhe, 1991
This talk will describe the visualization tools used in our scientific computing group to look at data and functions in two and three space variables. Emphasis is given to aspects that differ from the prevailing style elsewhere, and the points made will be illustrated with a videotape of representative example of the tools in use.
Aside from a few inherently interactive tools such as brushing scatterplots and choosing viewpoints, we emphasize images recorded frame-at-a-time onto videotape. Sound works effectively for presenting scalar information in sync with field displays, for adding tick marks on the time axis, and for more subtle stretched data displays.
Eric Grosse, How Shall We Connect Our Software Tools Visualization'91 Proceedings, IEEE Computer Society Press, 1991
Traditionally we connect our software tools using human-readable files. This is a conscious decision to buy flexibility and understandability at some cost in performance relative to binary file formats. This note explores the possibility of using shared memory functions to retain most of the existing style while leapfrogging the speed of reading binary files, at least in some environments and for some applications.
version of 91-07 which includes figure
Coughran and Grosse, Seeing and Hearing Dynamic Loess Surfaces Interface'91 Proceedings, 1991, Springer
Why would a visually oriented person use sound? Not to replace a line drawing, but to recall one while looking at something else. Or to add tick marks along the time axis. Or, if it doesn't cost anything, to add background on the off chance that the stretched display will reveal something not noticed in the line drawing. This talk will include a video giving real examples in which data features were heard before seen. It will also introduce the use of dashed surfaces to display standard errors.
Robert Fourer and David M. Gay, "Expressing Special Structures in an Algebraic Modeling Language for Mathematical Programming", 30 May 1991.
A knowledge of the presence of certain special structures can be advantageous in both the formulation and solution of linear programming problems. Thus it is desirable that linear programming software offer the option of specifying such structures explicitly. As a step in this direction, we describe extensions to an algebraic modeling language that encompass piecewise-linear, network and related structures. Our emphasis is on the modeling considerations that motivate these extensions, and on the design issues that arise in integrating these extensions with the general-purpose features of the language. We observe that our extensions sometimes make models faster to translate as well as to solve, and that they permit a ``column-wise" formulation of the constraints as an alternative to the ``row-wise" formulation most often associated with algebraic languages.
David M. Gay, "Automatic Differentiation of Nonlinear AMPL Models", 22 Aug. 1991.
Cleveland and Grosse, Computational Methods for Local Regression Statistics and Computing, 1991, 1:1, 47-62
Local regression is a nonparametric method in which the regression surface is estimated by fitting parametric functions locally in the space of the predictors using weighted least squares in a moving fashion similar to how a time series is smoothed by moving averages. Three computational methods for local regression are presented. (1) Fast surface evaluation is achieved by building a $k$-$d$ tree in the space of the predictors, evaluating the surface at the corners of the tree, and then interpolating elsewhere by blending functions. (2) Surfaces are made conditionally-parametric in any proper subset of the predictors by a simple alteration of the weighting scheme. (3) Degree-of-freedom quantities that would be extremely expensive to compute exactly are approximated, not by numerical methods, but through a statistical model that predicts the quantities from the trace of the hat matrix, which can be computed easily.
David M. Gay and Linda Kaufman, Tradeoffs in Algorithms for Separable Nonlinear Least Squares
When nonlinear least squares problems are separable, i.e., some parameters appear linearly, it is often useful to project the linear parameters out of the problem, which leaves a nonlinear least-squares problem involving only the nonlinear parameters. For large-residual problems, it saves iterations but costs work and storage to use an ``augmented model'' in solving this problem. When there are multiple right-hand sides, the costs can be large, making a Levenberg-Marquardt or even a normal-equations algorithm more attractive; for some such problems, the associative law and extra orthogonal transformations can significantly reduce operation counts.
David M. Gay, Correctly Rounded Binary-Decimal and Decimal-Binary Conversions
This note discusses the main issues in performing correctly rounded decimal-to-binary and binary-to-decimal conversions. It reviews recent work by Clinger and by Steele and White on these conversions and describes some efficiency enhancements. Computational experience with several kinds of arithmetic suggests that the average computational cost for correct rounding can be small for typical conversions. Source for conversion routines that support this claim is available from netlib.
N. L. Schryer, POST - A Package for Solving Partial Differential Equations in One Space Variable
Eric Grosse, Catalog of Algorithms for Approximation
This is an outline and a list of algorithms for numerical approximation, with references to the literature and pointers to available code. The database has been formatted here as an indented tree using TeX; alternatively, it may be viewed in graphical form or may be traversed using a C program or Hypercard, or keyword-searched using netlib email, or browsed as HTML.