Abstracts of Talks

A pdf file of all the abstracts, suitable for printing, is available here.

A Parallel Direct Solver for the Simulation of Large-scale Power/Ground Networks

Venkataramanan Balakrishnan, Purdue University

On Positivity of Multivariate Polynomials

B. Ross Barmish, University of Wisconsin

Abstract: In this talk, I will provide an overview of my recent collaborative work on the well known problem of polynomial positivity over a given domain. Motivated by NP-Hardness considerations, we introduce the so-called dilation integral in the context of a ``softening'' this problem. That is, rather than insisting that the polynomial is positive over the entire domain, we allow for a ``small'' volume of violation.

Arbitrary order Hessenberg-quasiseparable matrices and polynomials

Tom Bella, University of Rhode Island

Abstract: The classification of tridiagonal matrices in terms of polynomials orthogonal on a real interval, as well as the classification of unitary Hessenberg matrices in terms of Szegö polynomials (orthogonal on the unit circle) are well-known results, and form the basis for many fast algorithms involving these classes. In this talk, we give complete classifications of matrices having Hessenberg structure as well as quasiseparable structure of arbitrary order in terms of the polynomials related in the same way as the above examples. Several subclasses are also classified, including Hessenberg-semiseparable matrices, and the motivating special cases of tridiagonal and unitary Hessenberg matrices.

Graphs and Matrices

Avi Berman, Technion - Israel Institute of Technology

Abstract: In the talk I will discuss a personal choice of examples of the fascinating interrelation between Matrix Theory and Graph Theory.

Multiple Proofs and Motivating Examples in Teaching Linear Algebra

Avi Berman, Technion - Israel Institute of Technology

Abstract: In this talk I will describe two approaches to teaching linear algebra and some thoughts on how to combine them.

Robust Control via Sign Definite Decomposition

S.P. Bhattacharyya, Texas A&M University

Joint work with L.H. Keel

Abstract: We present some new results on multivariable fixed order control using sign definite decomposition. The main result is a Kharitonov type stability test that can be used in a recursive and modular fashion to construct stabilizing and performance attaining sets. The results are illustrated by examples.

Eigenvalues of Digraphs, with emphasis on the spectral radius: A Survey

Richard A. Brualdi, University of Wisconsin - Madison (USA)

Abstract: Spectral Graph Theory (SGT) is a rich and well-developed subject which continues to be heavily researched. Since the adjacency matrix (or Laplacian matrix) of a graph G is a real symmetric matrix, the spectrum (or Laplacian spectrum) of a graph is real. SGT relies heavily on the characterization of the eigenvalues of a real symmetric matrix by Rayleigh quotients.

Spectral Digraph Theory (SDT) is less well-developed. The adjacency matrix of a digraph D is a nonnegative matrix, and in general, the spectrum of D contains complex eigenvalues. But, by the Perron-Frobenius theory of nonnegative matrices, D has a nonnegative eigenvalue that is greater than or equal to the absolute value of all the other eigenvalues of D. This eigenvalue is called its Perron eigenvalue, and it equals the spectral radius of D. Much, but not all, of the research in SDT is focused on the Perron eigenvalue: lower and upper bounds, or the maximum and the minimum of the Perron eigenvalue over well-defined classes of digraphs of interest. Other research includes determination of cospectral digraphs, identification of regions in the complex plane containing the entire spectrum, special properties of the spectrum of certain kinds of digraphs, etc.

In this talk we shall survey certain parts of SDT.

Stabilized completions of general differential algebraic equations

Steve Campbell, North Carolina State University

Abstract: Differential algebraic equations (DAEs) are a natural way to model a wide variety of physical phenomena. All numerical methods for DAEs must, in some manner, construct a differential equation (ODE) that can be integrated. Sometimes this is done by determining an ODE on a submanifold and sometimes this is done by building an ODE, called a completion of the DAE, which includes the DAE solutions. A number of useful results have been developed which exploit the structure of specific problems. But the increasing use of composite models drawn from different disciplines means this structure may not be there. Also a number of control problems do not have a predetermined structure. Recently there has been a renewed effort to construct stabilized completions of general DAEs strictly in terms of the original equations. This talk will introduce this problem, discuss some of the recent results and ongoing investigations, and time permitting some potential applications in control and simulation.

Banishing Runge, Avoiding Gibbs

S. Chandrasekaran, M. Gu, H. Mhaskar, J. Moffitt, K. Raghuram, N. Somasunderam

Abstract: It is well-known that approximating functions (even C^∞ ones) by interpolation using polynomials can be divergent. This is the famous Runge phenomenon. In this talk we show a very simple scheme to construct arbitrarily high-order interpolating polynomials at arbitrary interpolation points that is point-wise convergent. The method can be coded in a few lines of Matlab and easily extends to higher-dimensions. A linear time algorithm via HSS methods is available. There is a deep proof that the method works. We will discuss extensions of the method to noisy data when interpolation is not advisable and to handling jump discontinuities so as to avoid Gibbs phenomenon.

Computational and Optimization Methods for Quadratic Inverse Eigenvalue Problems In Active Vibration Control and Finite Element Model Updating

Biswa Nath Datta, Northern Illinois University

Abstract: This talk deals with two quadratic inverse eigenvalue problems that arise in mechanical vibration and structural dynamics. The first one, Quadratic Partial Eigenvalue Assignment Problem(QPEVAP), arises in controlling dangerous vibrations in mechanical structures, such as buildings, bridges, highways, automobiles, air and space crafts, and others. QPEVAP concerns with finding two feedback matrices such that a small amount of the eigenvalues of the associated quadratic eigenvalue problem are reassigned to suitably chosen ones while keeping the remaining large number of eigenvalues and eigenvectors unchanged. For robust and economic control design, these feedback matrices must be found in such a way that they have the norms as small as possible and the condition number of the modified quadratic inverse problem is minimized. These considerations give rise to two nonlinear unconstrained optimization problems, known respectively, as the Robust Quadratic Partial Eigenvalue Assignment Problem (RQPEVAP) and Minimum Norm Quadratic Partial Eigenvalue Assignment Problem (MNQPEVAP). The other one, Finite Element Model Updating Problem (FEMUP) arising in the design and analysis of structural dynamics, refers to updating an analytical finite element model so that a set of measured eigenvalues and eigenvectors from a real-life structure are reproduced and the physical and structural properties of the original model are preserved. A properly updated model can be used in confidence for future designs and constructions. Another major application of FEMUP is the damage detections in structures. Solutions of FEMUP also give rise to several constrained nonlinear constrained optimization problems.

We will give an overview of the recent developments on computational methods for these difficult nonlinear optimization problems and discuss directions of future research. The talk is interdisciplinary in nature and will be of interests to mathematicians, computational and applied mathematicians, and control and vibration engineers.

Linear Algebra with "Ghosts and Shadows"

Alan Edelman, MIT

Abstract: The standard numerical algorithms all have real and complex versions. Less known and less used are quaternion versions. We show how "random" matrices have a much richer possibility than the three famous division rings. We call these quantities "ghosts" and "shadows". Open problems include a theory to solidify what is happening and algorithmic techniques for computation. While the quaternions are hardly used we have reason to believe that in the decades to come, these generalizations will find wide applicability.

This represents joint work with Plamen Koev.

Synthetic Boundary Conditions, Coordinate Transformations and Preconditioning for Image Deblurring Problems

Ying Wai (Daniel) Fan and James Nagy, Emory University

Results and problems for 3-tensors

Shmuel Friedland, University of Illinois at Chicago

In this talk I state some results and open problems for 3-tensors:

The generic rank of 3-tensor over C and R; best rank one approximations in l₂ and l_p norm; Perron-Frobenius theorem for irreducible nonnegative tensors; low rank approximations of tensors; scaling of nonnegative tensors to balanced, (doubly stochastic), tensors.

A variant of this talk is available at http://www2.math.uic.edu/~friedlan/haifa5.09.pdf

Challenges in Combinatorial Scientific Computing

John R. Gilbert, University of California at Santa Barbara

Abstract: Computation on large combinatorial structures -- graphs, strings, partial orders, etc. -- has become fundamental in many areas of data analysis and scientific modeling. The field of high-performance combinatorial computing, however, is in its infancy. By way of contrast, in numerical supercomputing we possess standard algorithmic primitives, high-performance software libraries, powerful rapid-prototyping tools, and a deep understanding of effective mappings of problems to high-performance computer architectures.

This talk will describe several challenges for the field of combinatorial scientific computing in algorithms, tools, architectures, and mathematics. I will draw examples from several applications, and I will highlight our group's work on high-performance implementation of algebraic primitives for computation on large graphs.

Error analysis for least squares with monotonical data

Hongbin Guo, Arizona State University

Abstract: In kinetics analysis of biomedical engineering, linear methods are widely used to estimate parameters of biochemical and physiological processes. While biases are observed for linear least squares solutions of these linear models people usually account for the bias by color noise. In contrast, we characterize the linear approximation model error through the fact of monotonic structures of data, which is the case for dynamic Positron emission tomography (PET) quantification. We find that the bias due to linearization may be more significant than that due to noise and both under- and over-estimation may happen. We derive conditions under which linear methods either under- or over-estimates the parameters. The error caused by model error is bounded analytically. The results are validated through dynamic PET data for brain function measurements.

Direct Trajectory Optimization and Costate Estimation of General Optimal Control Problems Using a Radau Pseudospectral Method

Divya Garg, Michael A. Patterson, Camila Francolin, Christopher L. Darby, Geoffrey T. Huntington, William W. Hager, and Anil V. Rao

Abstract: A method is presented for direct trajectory optimization and costate estimation using global collocation at Legendre-Gauss-Radau (LGR) points. A key feature of the method is that it provides an accurate way to map the KKT multipliers of the nonlinear programming problem to the costates of the optimal control problem. More precisely, it is shown that the dual multipliers for the discrete scheme correspond to a pseudospectral approximation of the adjoint equation using polynomials one degree smaller than that used for the state equation. The relationship between the coefficients of the pseudospectral scheme for the state equation and for the adjoint equation is established. Also, it is shown that the inverse of the pseudospectral LGR matrix is precisely the matrix associated with an implicit LGR integration scheme. Hence, the method presented in this paper can be thought of as either a global implicit integration method or a pseudospectral method. Numerical results show that the use of LGR collocation leads to the ability to determine accurate primal and dual solutions for both finite and infinite-horizon optimal control problems.

Connectivity Constrained Reference Basis Model Updating

Yoram. Halevi, Technion -- Israel Institute of Technology

Abstract: Model updating is a mathematical procedure of correcting an analytical model, almost exclusively based on the Finite Element method (FEM), using experimental data. As in most other methods, the experimental data in the Reference Basis (RB) method is modal, i.e. some natural frequencies and their corresponding modeshapes. In the general framework of standard RB, certain quantities are considered to be completely accurate and those that are free (generally the stiffness and the mass matrices) should satisfy the relationships that must hold in a passive vibrating structure, while their deviation from the analytical model is minimal. They are updated by solving a constrained optimization problem. The RB method possesses some clear advantages. The updated system eigendata coincide with the measured one, an obvious requirement that some other methods fail to achieve. It is based on a reasonable, and well-defined, optimization criterion, and presents a closed form solution of the problem. Moreover, and perhaps most importantly, the dimension that dominates the required computational effort is the number of measured modes, compared to the number of degrees of freedom in other methods. Since the two usually differ by orders of magnitude, the reference basis method is much more efficient and can handle models having a high dimension. The standard reference basis method has also a major disadvantage, which prevents it from becoming a leading and vastly applied method. The updated model has no relationship with physical parameters, nor does it preserve the connectivity of the system. As a result it generally produces stiffness elements (nonzero matrix entries) between degrees of freedom that might be way apart. Another problem with the method is that it cannot incorporate any prior knowledge or engineering consideration into the process.

Connectivity Constrained Reference Basis (CCRB) is a method for introducing connectivity constraints into reference basis. It combines the parametric setup of sensitivity methods with the RB algorithm. The tool that enables it is a judicious and adaptive choice of the weighting matrices in the RB procedure. The key step in CCRB is the a posteriori connectivity assignment, which enables maintaining the advantages of RB, e.g. eigendata matching and low computation requirements. This step is repeated recursively until the solution of a generalized RB problem approaches satisfaction of the connectivity constraints in a natural manner. The method uses the notions of connectivity cost and parameterization cost to obtain the best model for a given parameterization and to compare the outcomes of different parameterizations.

The talk will address some theoretical issues concerning RB and CCRB including the interpretation of the algorithm as a projection, the geometrical properties of the projections, and the apparently immanent interconnection between connectivity enforcing and sensitivity to measurement noise.

Can Any Reduced Order Model Be Obtained Via Projection?

Yoram. Halevi, Technion -- Israel Institute of Technology

Abstract: The talk will discuss the properties of general reduced order models obtained by projection of a higher order system. It answers questions such as, are any two models of different orders related by a projection? Is it possible to obtain the same reduced order model using different projections? How to find, if it exists, a projection that relates the two models?, etc. It is shown that answers to those questions can be obtained by investigating the properties of a certain matrix pencil. The key tool is the Kronecker canonical form, and in some cases of square systems the problem becomes that of generalized eigenvalues. The optimal L2 reduced order model was also investigated in this context. Combining the L2 optimality conditions into that framework gives a different point of view on the optimal reduced order model. It is shown that the zeros of the optimal approximation error transfer function are the mirror image of the reduced model poles with the same multiplicity in non-square systems, and doubled multiplicity in square systems. It is also shown that in some cases the optimal L2 reduced order model resides on the boundary of the set of models that can be obtained by projection.

Stochastic-Volatility, Jump-Diffusion Optimal Portfolio Problem with Jump-Bankruptcy Condition

Floyd B. Hanson, Universities of Illinois and Chicago

Merton's risk-averse optimal portfolio problem with consumption in continuous time is given more realism with stochastic jumps and volatility processes added to the usual diffusion process. This includes the effects of large and variable fluctuations, excluded by probability conditions of the diffusion approximation. The stochastic-volatility, jump-diffusion (SVJD) leads to a stochastic system with a discontinuous state space and variable volatility as found with bear and bull rallies. The Hamilton-Jacobi Bellman equation is derived and the no-bankruptcy or positive wealth argument in the compound jump arguments implies additional restrictions on the instantaneous stock fraction. These restrictions are very reasonable, yet wide and finite, when the jump-amplitude distribution has finite support, but if the distribution has infinite support, such as commonly used normal or exponential, then reasonable short-selling and borrowing are restricted to much more narrow range. Further, computational procedures are treated in the case of the constant relative risk aversion (CRRA) utility with modifications given beyond the diffusion model treatment. Computational and theoretical problems with the popular Heston square root stochastic volatility model are also discussed and a scaling remedy is given.

The extended Krylov subspace method and orthogonal Laurent polynomials

Carl Jagels, Hanover College

Abstract: The need to evaluate expressions of the form f(A)v, where A is a large sparse or structured symmetric matrix, v is a vector, and f is a nonlinear function, arises in many applications. The extended Krylov subspace method can be an attractive scheme for computing approximations of such expressions. This method projects the approximation problem onto an extended Krylov subspace

Compressed Sensing and Matrix Problems

In-Jae Kim, Minnesota State University - Mankato

Abstract: This is an introductory talk on compressed sensing. Some background material and matrix problems related to compressed sensing will be presented.

Constructing Nonnegative Matrices With Given Nonzero Spectrum

Thomas J. Laffey, University College Dublin, Ireland

Abstract: Let σ =( λ ₁, ... , λ _n) be a list of complex numbers and let s_k:= λ₁^k+ ... + λ_n^k, k=1,2,3,... The nonnegative inverse eigenvalue problem (NIEP) asks for necessary and sufficient conditions on σ in order that it be the spectrum of an entry-wise nonnegative matrix. If this occurs, we say that σ is realizable, and we call a nonnegative matrix A with spectrum σ a realizing matrix for σ. A necessary condition for realizability coming from the Perron-Frobenius theorem is that there exists j with λ _j real and |λ _i| ≤ λ _j, for all i. Such a λ_j is called a Perron root of σ. A more obvious necessary condition is that all the s_k are nonnegative.

In terms of n, a complete solution of the NIEP is only available for n ≤ 4. The solution for n=4, expressed in terms of inequalities for the s_k, appears in the PhD thesis of my former student ME Meehan (1998) and a solution in terms of the coefficients of the characteristic polynomial has been published recently by Torre-Mayo et al. (LAA 426 (2007)). However, the same problem in which one may augment the list σ by appending an arbitrary number N of zeros was solved by Boyle and Handelman (Ann.Math 133 (1991)). They proved the remarkable result that if σ has a Perron element and s_k ≥ 0 for all positive integers k (and s_m=0 for some m implies s_h=0 for all positive divisors h of m), then σ_N:=( λ₁, ... , λ _n, 0, ... ,0) (N zeros) is realizable. However, their proof is not constructive and does not provide a bound on the minimal number N=N( σ ) required for realizability.

I propose to discuss some recent progress, obtained jointly with Helena Šmigoc, on the following problem. Given σ satisfying the Boyle-Handelman conditions, find “good” upper and lower bounds on the minimum number N required for the realizability of σ _N. I will discuss an approach via power series, related to work of Kim, Ormes and Roush (JAMS 13(2000)).

Linear Algebra Education Reform: Accomplishments of the Past and Challenges for the Future

Steven J. Leon, University of Massachusetts Dartmouth

Abstract: The first part of the talk will survey some of the work that has been done to reform linear algebra education during the past 20 years. In particular we will focus on the work done by the Linear Algebra Curriculum Study Group (1990), the work of the Education Committee of the International Linear Algebra Society (ILAS), and the results of the ATLAST workshops (1992-1997). Issues discussed will include: linear algebra curriculum, pedogogy, the use of software and technology, and undergraduate research projects. While the work of the past 20 years has resulted in many improvements to linear algebra education, there is much in the way of reform that still needs to be accomplished. The second part of the talk will focus on the challenges for the future and how we can go about meeting those challenges.

Compressive sensing matrices and coded aperture imaging

Roummel F. Marcia (UC Merced) and Rebecca M. Willett (Duke University)

Estimating Computational Noise in Simulation-Based Optimization Problems

Jorge Moré, Argonne National Laboratory

Joint work with Stefan Wild

Abstract: What is computational noise? What are noisy optimization problems? These questions are of importance in the simulation of complex scientific phenomena with optimization techniques. We outline a theoretical framework for studying computational noise in simulation-based optimization problems of the form

Our approach defines computational noise in terms of a stochastic model, but we show that this model applies to deterministic complex optimization problems. We also present an algorithm for determining the computational noise in a simulation. We show that in most cases we can reliably determine the computational noise with 7 evaluations of the simulation. We illustrate our results with several new and interesting simulation-based optimization problems.

A Receptance Method for Active Pole Placement in Structures: Sensitivity, Partial Pole Placement and Robustness

John E Mottershead and Maryam Ghandchi Tehrani, University of Liverpool, UK
j.e.mottershead@liv.ac.uk

Abstract: The problem of active pole placement in vibrating structures is addressed by using receptance measurements from a vibration test. The use of receptances, rather than the usual system matrices, M, C, K, is shown to have several advantages. In particular the quality of modern measured data is generally thought to be better than the representation obtained from a finite element model, which contains approximations, assumptions and modelling errors. An important aspect of the FE modelling error is the limitation to a finite number of degrees of freedom, whereas probably most engineering structures are continuous in the sense that the number of natural frequencies is effectively uncountable. It is always possible to write a set of complete receptance equations from the available measurement input and output data from a modest number of actuators and sensors. However, dynamics-stiffness equations require a full set of states for completeness, which is the reason for model reduction and the estimation of unmeasured states using an observer (or equivalent).

Eigenvalue sensitivity equations are developed for the cases of small perturbations to the measurements and to the controller gains. It is demonstrated that partial pole placement using M, C, K relies upon the choice of a controller that renders the unchanged eigenvalues unobservable. The dual of this approach is to choose the input so that the unchanged eigenvalues become uncontrollable. Advantages and disadvantages of the two approaches are discussed. For robust pole placement it is necessary that the eigenvalue sensitivity matrix is well conditioned. The problem of destabilisation of unknown high-frequency modes is addressed by constraints to ensure that the Nyquist criterion is satisfied within chosen gain and phase margins.

Numerical examples and practical implementation of partial pole placement using inertial actuators and accelerometers by the receptance method are described. In the case of experimental implementation, use of the voltage/acceleration transfer function (rather than the receptance) obviates the need to determine the actuator gain. Placement of actuator poles, which may otherwise be destabilised by spillover effects, is achieved by use of a further accelerometer and a nested feedback arrangement.

Efficient Iterative Methods for Large Scale Inverse Problems

James Nagy, Emory University

Abstract: Ill-posed problems arise in many image processing applications, including microscopy, medicine and astronomy. Iterative methods are typically recommended for these large scale problems, but they can be difficult to use in practice. In this talk we describe a hybrid approach that combines the Golub-Kahan bidiagonalization algorithm with Tikhonov regularization and a weighted generalized cross validation scheme. Applications from image processing illustrates the effectiveness of the resulting numerical scheme. This is joint work with Julianne Chung.

On the connections between the inverse M-matrix problem and the inverse mean first passage matrix problem for Markov chains

Michael Neumann, University of Connecticut

Abstract: The inverse M-matrix problem is to identify when an nxn nonnegative matrix A is an inverse of an M-matrix? We now define the inverse mean first passage matrix as follows: Given an nxn positive matrix M, then when does there exist a discrete time Markov chain on n states such that M is the mean first passage matrix for the chain?

Three papers from the 1990's by Tetali (1994), by Xue (1997), and by Fiedler (1998) directly or indirectly hint that the two problems are linked. We shall now make the link explicit. We shall see that the inverse M-matrix problem that we are speaking of here is for the inverse of a diagonally dominant M-matrix.

This is joint work with Dr. Nung-Sing Sze of the University of Connecticut

M_v-matrices: A generalization of M-matrices based on eventually nonnegative matrices

Dale Olesky, University of Victoria

Abstract: An M_v-matrix has the form A=sI-B, where s≥ρ(B)≥0 and B is eventually nonnegative; i.e., B^k is entrywise nonnegative for all sufficiently large integers k. A theory of M_v-matrices is developed that parallels the theory of M-matrices, in particular as it regards exponential nonnegativity, spectral properties, semipositivity, monotonicity, inverse nonnegativity, and diagonal dominance.

This is joint work with Michael Tsatsomeros and Pauline van den Driessche.

A quasiseparable approach to CMV and Fiedler matrices

Vadim Olshevsky, University of Connecticut

Abstract: Several new classes of five-diagonal matrices have been introduced recently. Specifically, there are two classes of matrices, called CMV and Feidler matrices that were are found to be related to polynomials orthogonal on the unit circle and Horner polynomials, respectively. We start with an observation that both classes belong to a wider class of we call twisted Hessenberg-Order-One quasiseparable matrices. This observation leads to a number of generalizations of known results. We obtain full desriptions of such five-diagonal matrices in terms of the recurrence relations satisfied by the characteristic polynomials of their principal submatrices.

Joint work with Tom Bella, Gil Strang, and Pavel Zhlobih

Tensor and Segmentation Methods for Hyperspectral Unmixing

Bob Plemmons, Wake Forest University

Abstract: An important problem in hyperspectral image data analysis is to identify materials present in the object or scene being imaged and to quantify their abundance in the mixture. We discuss and compare two approaches for this problem: 1) algebraic techniques based on tensor decompositions and multi-way analysis, and 2) coupled segmentation and denoising/deblurring models based on fuzzy piecewise constant segmentation and fast total variation regularized denoising/deblurring.

Numerical results are reported for a hyperspectral data material identification problem in remote sensing.

This work is joint with Fang Li, Michael Ng, Paul Pauca, Han Wang and Peter Zhang.

A Subsolution Method for the Scattering Amplitude

Paul Saylor, Louisiana State University and University of Illinois, Urbana

Abstract: The scattering amplitude (defined below) arises in numerous applications such as (1) radar simulation; and (2) simulation of tools for identifying petroleum deposits. The scattering amplitude is a mere scalar yet one typically requiring the solution of huge linear systems. Certain algorithms for this important HPC application downplay the linear system solution by seeking an expression involving the solution only indirectly. A method to obtain only a function of the solution is called a subsolution method. The characteristic lack of explicit dependence on the solution affects organization of the work.

This is part of a joint project with Gerry Minerbo, Dennis Smolarski and the late Gene Golub. (Given nonsingular matrix A and column vectors b and c, if M denotes the inverse of A, the scattering amplitude is defined to be c * Mb.)

Visualization in max algebra: An application of diagonal scaling of matrices

Hans Schneider, University of Wisconsin - Madison

Abstract: A square nonnegative matrix is called visualized if all its elements are less than or equal to its maximum cycle mean. A visualized matrix is called strictly visualized if those elements that equal the maximum cycle mean lie on the critical graph. Every nonnegative matrix is diagonally similar to a strictly visualized matrix. When the matrix is irreducible there exists a strictly visualized canonical form. This was proved by H.S and M.H.Schneider about 20 years ago. We discuss the diagonal scaling background used in the proof of this result. We also present some results in max algebra (aka tropical algebra) that have been proved using visualization. These are contained in a recent paper by Sergeev-S-Butkovic "On visualization scaling, subeigenvectors and Kleene stars in max algebra" which may be found on the LAA website.

Expected values of parameters associated with the minimum rank of a graph

Tracy Hall (Brigham Young University), Leslie Hogben (Iowa State University), Ryan Martin (Iowa State University) and Bryan Shader (University of Wyoming)

Abstract: We investigate the expected value of various graph parameters associated with the minimum rank of a graph, including minimum rank/ maximum nullity and related Colin de Verdiere-type parameters. Let G(v,p) denote the usual random graph on v vertices with edge probability p. We obtain bounds for the expected value of the random variables mr(G(v,p)), M(G(v,p)), ν(G(v,p)) and ξ(G(v,p)), which yield bounds on the average values of these parameters over all labeled graphs of order v.

Partial Spectrum Assignment in a Time Delayed System for Active Vibration Control

Kumar Vikram Singh, Miami University, Oxford, OH

Abstract: Partial spectrum assignment problems in active control deals with reassigning a small set of unwanted eigenvalues and/or eigenvectors by using feedback control force to suitably chosen desired location without altering the remaining spectrum. Real time implementation of such an active control strategy requires incorporation of the inherent time delay in the feedback loop for control gain computations. In this presentation, numerical algorithms for obtaining such control gains for active spectrum assignment will be presented. Some potential applications of partial spectrum assignment in active aeroelastic control, effect of the time delay in stability, and applications of such a control strategy in real life engineering problems as well challenges in implementing them will be highlighted.

A New Hybrid Method for the Quadratic Affine Inverse Eigenvalue Problem

Biswa N. Datta and Vadim Sokolov, Northern Illinois University

Abstract: The Quadratic Inverse Eigenvalue Problem (QIEP) is to find three matrices, M, C, and K, given a set of numbers and vectors, such that the given numbers become the eigenvalues of the matrix pencil λ² M +λ C + K with the given vectors as the associated eigenvectors. The Quadratic Affine Inverse Eigenvalue Problem (QAIEP) has the additional requirement that the matrices M, C, and K must belong to an affine class of matrices, meaning that these are linear combinations of a given set of structured matrices.

In this talk, we propose a new hybrid method for the solution of the QAIEP. The validity of the method is illustrated by means of a numerical example of spring-mass system.

Implementing Numerical Linear Algebra in the Undergraduate Science and Engineering Curriculum

Ronald F. Taylor, Wright State University

Abstract: A key to the success of the professional development of undergraduate science and engineering students is a clear understanding of the methods of numerical linear algebra with applications. Transitioning students from an introductory mathematics course in linear algebra to a computational course offers many challenges and opportunities. Several non-trivial models drawn from aerospace and roadway vehicle dynamic simulations are presented which form a basis for course modules in various settings. Emphasis is on computation of rates of change of eigenvalues with respect to problem parameters for design optimization studies. Mathematical models leading to nonsymmetric matrices with eigenvalues coalescence behavior are presented as computational challenges for the advanced undergraduate. Educational initiatives in computational science which make use of such course modules are also discussed.

A New Hybrid Method for Finding Eigenpairs of a Symmetric Quadratic Eigenvalue Problem in an Interval

Karabi Datta, Yoopyo Hong, and Mohan Thapa, Northern Illinois University

Abstract:
The symmetric quadratic eigenvalue problem (λ²M + λ C + K)u = 0, where M, C, and K are given n × n matrices and (λ, u) is an eigenpair, arises in a wide variety of practical applications, including vibration, acoustic, and noise control analysis. In the most practical application, the problem is often of a very large dimension. Unfortunately because of the nonlinearity, the problem is extremely hard to solve numerically. The state-of-art computational techniques, such as the Jacobi-Davidson method, are capable of computing only a few extremal eigenvalues and eigenvectors if the initial vector is chosen properly. Fortunately, there are engineering applications that require only some of the eigenvalues lying within an interval. In this paper, a New Hybrid Method combining a Modified Parametrized Newton-type method with the Jacobi-Davidson method is proposed to compute eigenpairs of a quadratic pencil within an interval. The experimental results show that this method is much faster than the Jacobi-Davidson method.

On nonautonomous linear systems of differential and difference equations with R-symmetric coefficient matrices

William Trench, Trinity University

Abstract

Explicit Sensor Network Localization using Semidefinite Programming and Clique Reductions

Nathan Krislock and Henry Wolkowicz, University of Waterloo

Abstract: The sensor network localization, SNL, problem in embedding dimension r, consists of locating the positions of ad hoc wireless sensors, given only the distances between sensors that are within radio range and the positions of a subset of the sensors (called anchors). There are advantages for formulating this problem as a Euclidean distance matrix completion, EDMC, problem, and ignoring the distinction between anchors and sensors. Current solution techniques relax this problem to a weighted, nearest, (positive) semidefinite programming, SDP, completion problem, by using the linear mapping between EDMs and SDP matrices. The relaxation consists in ignoring the rank r for the SDP matrices. The resulting SDP is solved using primal-dual interior point solvers, yielding an expensive and inexact solution.

Moreover, the relaxation is ill-conditioned in two ways. First, it is implicitly highly degenerate in the sense that the feasble set is restricted to a low dimensional face of the SDP cone. This means that the Slater constraint qualification fails. Second, nonuniqueness of the optimal solution results in large sensitivity to small perturbations in the data.

The degeneracy in the SDP arises from cliques in the graph of the SNL problem. These cliques implicitly restrict the dimension of the face containing the feasible SDP matrices. In this paper, we take advantage of the absence of the Slater constraint qualification and derive a technique for the SNL problem, with exact data, that explicitly solves the corresponding rank restricted SDP problem. No SDP solvers are used. We are able to efficiently solve this NP-hard problem with high probability, by finding a representation of the minimal face of the SDP cone that contains the SDP matrix representation of the EDM. The main work of our algorithm consists in repeatedly finding the intersection of subspaces that represent the faces of the SDP cone that correspond to cliques of the SNL problem.

A stable and highly efficient superfast Toeplitz solver

Jianlin Xia, Purdue University

Abstract: In this talk, we will discuss a new stable and superfast solver for Toeplitz linear systems. With the displacement structure, our method solves the Cauchy-like system converted from the Toeplitz system in nearly O(N) flops with a small constant. Strong rank revealing LU factorizations are used in a hierarchical scheme to work on two levels of structured representations. The method is significantly faster than some existing superfast Toeplitz solvers such as a previous one by the authors in [SIMAX, 2007]. This is joint work with Ming Gu.

Matrix Computation in Numerical Polynomial Algebra and Algebraic Geometry

Zhonggang Zeng, Northeastern Illinois University

Abstract: Numerical computation in polynomial algebra and algebraic geometry emerges as a fast growing field of study in recent years. In an area dominated by symbolic computation for decades, developing numerical algorithms for polynomial problems leads to many new challenges, such as handling ill-posedness. On the other hand, numerical polynomial algebra is a natural extension and an application area of numerical linear algebra, as matrix computation plays an indispensible role. This talk introduces the matrix computation strategies in numerical polynomial algebra and numerical algebraic geometry using several case studies with computing results.

Matrix Representations of Sturm-Liouville Problems with Finite Spectrum

Qingkai Kong, Hans Volkmer and Anton Zettl

Abstract: We identify a class of Sturm-Liouville equations such that any Sturm-Liouville (SL) problem consisting of such an equation and an arbitrary separated or coupled real self-adjoint boundary condition has a representation as an equivalent finite dimensional matrix eigenvalue problem. Conversely, given any matrix eigenvalue problem of certain type and an arbitrary separated or coupled real self-adjoint (SL) boundary condition, we construct a class of Sturm-Liouville problems with the specified boundary condition, each of which is equivalent to the given matrix eigenvalue problem.

Contractions and Hua Matrices

Fuzhen Zhang, Nova Southeastern University

Abstract: Late Chinese mathematician L-K Hua showed an elegant determinant inequality for contractive matrices in 1955. His study was followed by M. Marcus, R. Bellman, T. Ando, C. Paige, G.P.H. Styan, B-Y Wang. The purpose of this talk is to revisit the Hua's original work, show new results, and to present some open problems on the topic.

Colorful Quaternions

Fuzhen Zhang, Nova Southeastern University

Abstract: We will show some beautiful quaternion fractals, mention applications of quaternions in Control Theory, Signal Processing, Computer graphics, quantum physics, and present most recent development of quaternion matrix theory, particularly the eigenvalue problems.

A Derivative-Free Algorithm for the Least-Square Minimization

Hongchao Zhang, Louisiana State University

Abstract: We develop a framework for a class of derivative-free algorithms for the least-squares minimization problem. These algorithms are based on polynomial interpolation models and are designed to take advantages of the problem structure. Under suitable conditions, we establish the global convergence and local quadratic convergence properties of these algorithms. Promising numerical results indicate the algorithm is efficient and robust when finding both low accuracy and high accuracy solutions. Comparisons are made with standard derivative-free software packages that do not expoit the special structure of the least-squares problem or that use finite differences to approximate the gradients.

Linear Programming over Cones and Linear Semi-infinite Programming

Qinghong Zhang, Northern Michigan University

Abstract: Linear semi-infinite programming problems (LSIPs) and linear programming problems (LPs) over cones are two extensions of the ordinary linear programming problem. At a first glance, LSIPs are different from LPs over cones. However, by defining appropriate cones, we can reformulate an LSIP as LPs over cones. In this reformulation, we can use the results, which are available for LPs over cones, to derive the results for LSIPs. Specifically, the duality results via a minimal cone approach for LPs over cones can be applied to LSIPs. The moment cones and the characteristic cone for an LSIP, which play very important roles in the duality theory of LSIPs, have new descriptions via this approach. Results pertaining to the geometry of the set of the feasible solutions for the primal LSIP and the optimality criteria for the dual LSIP are also discussed. For a given LP over cone, the problem data is referred to as a data instance. Given fixed vector spaces and a convex cone appearing in the formulation of an LP over cones, the set of all the data instances becomes a normed linear space with an appropriately defined norm. The characterizations of the interiors and boundaries of the feasible and infeasible instances have been studied in the literature. In this talk, connections between interiors and boundaries of feasible and infeasible data instances and weak and strong feasibilities of the primal-dual pair for an LP over cones are made.