From bazara at sandia.gov Thu Aug 8 11:59:50 2002 From: bazara at sandia.gov (Zaragoza, Barbara) Date: Mon Oct 23 09:14:12 2006 Subject: [CSRI/CSMR Seminars] CSRI Seminar Series - Todd S. Munson - August 19, 2002 Message-ID: Computational Sciences and Mathematics Research (CSMR) Presents A Study in Support Vector Machines Todd S. Munson Argonne National Laboratory Date: Monday, August 19, 2002, 10 a.m. (PST) Location: Bldg. 921, Rm. 137(Sandia-CA)/Building 980, Rm. 95 (Sandia-NM) ABSTRACT: We discuss interior-point and semismooth methods for solving quadratic programming problems with a small number of linear constraints where the quadratic term consists of a low-rank update to a positive semi-definite matrix. Several formulations of the support vector machine, a technique employed by the machine learning community for supervised learning, fit into this category. A related example is the Huber regression problem, which can also be posed as a quadratic program with the desired properties. Support vector machines can be used, for example, when determining whether a tumor is malignant or benign. An interesting feature of the problems we consider is the volume of data, which can lead to quadratic programs with between 5 and 100 million variables and, if written explicitly, a dense $Q$ matrix. The implementations of the two algorithms use linear algebra specialized for the support vector machine application. For the targeted massive problems, all data is stored out-of-core and we overlap computation and I/O to reduce overhead. Results are reported for several linear support vector machine formulations demonstrating that the algorithms developed are reliable and scalable. ABOUT THE SPEAKER: Todd Munson works at Argonne National Laboratories in the Mathematics and Computer Science Division. His primary research focus is on algorithms and applications of complementarity. He has worked on two generalized Newton methods for solving these problems, one based on the Fischer-Burmeister reformulation and the other on the normal map reformulation. Each of these reformulations results in a nonsmooth system of equations to be solved. Implementations of these methods are available in the SEMI and PATH codes. Todd's recent work has been on a project to develop methods for solving optimization problems governed by partial differential equations. These are large nonlinear programming problems where parallel algorithms are needed. This work is part of the TOPS center. Todd received his Ph.D. in Computer Science from the University of Wisconsin in 2000 and has been a postdoctoral researcher at Argonne since then. Contact: Tamara Kolda (8950), (925) 294-4769, tgkolda@sandia.gov This seminar series is hosted by the CSMR Department at Sandia National Labs in Livermore, CA. For more information on upcoming events in The CSMR Department, visit http://csmr.ca.sandia.gov/news.html. For more information on The Computer Science Research Institute (CSRI) at Sandia National Labs in Albuquerque, NM, visit http://www.cs.sandia.gov/CSRI. From bazara at sandia.gov Mon Aug 12 15:12:45 2002 From: bazara at sandia.gov (Zaragoza, Barbara) Date: Mon Oct 23 09:14:12 2006 Subject: [CSRI/CSMR Seminars] CSRI Seminar Series - Professor Anne Greenbaum - August 22, 2002 Message-ID: The Computer Science Research Institute (CSRI) Presents Theory and Applications of the Polynomial Numerical Hull Professor Anne Greenbaum University of Washington Math Department Date: Thursday, August 22, 2002 - 1:00 p.m. (PST) Location: Bldg. 921, Rm. 137(Sandia-CA) / Bldg. 980, Rm. 24 (Sandia-NM) ABSTRACT: The asymptotic behavior of a matrix or linear operator is governed by its eigenvalues, but, in general, the transient behavior is not. Yet this transient behavior is often important in physical applications such as convection and fluid flow and in numerical algorithms such as finite difference schemes and iterative methods for solving linear systems. In this talk we consider sets associated with a matrix $A$ that are designed to give more information than the spectrum alone can provide about this transient behavior. Specifically, we discuss the {\em polynomial numerical hull of degree $k$}, which is defined as the set of points $z$ in the complex plane for which $\| p(A) \| \geq | p(z) |$ for all polynomials $p$ of degree $k$ or less. Geometrical properties and methods for computing these sets are discussed. As a sample application, we show how these sets can be used to predict cutoff phenomena in Markov chains, such as the much-publicized result that it takes seven riffle shuffles to randomize a deck of cards. ABOUT THE SPEAKER: Professor Anne Greenbaum is a member of the University of Washington, Mathematics Department since 1997. Prior to this position, she was a research professor at the Courant Institute of Mathematical Sciences and a Mathematician at LLNL. Professor Greenbaum's professional activities include being a member of the SIAM Council and SIAM Program Committee. She is the author of three books, the most recent one, "Iterative Methods for Solving Linear Systems"; she has also refereed numerous publications. Professor Greenbaum received both her Ph.D and Master's degrees from the University of California, Berkeley Contact: Victoria Howle, (8950), (925) 294-2204, vehowle@sandia.gov This seminar series is hosted by the CSMR Department at Sandia National Labs in Livermore, CA. For more information on upcoming events in The CSMR Department, visit http://csmr.ca.sandia.gov/news.html. For more information on The Computer Science Research Institute (CSRI) at Sandia National Labs in Albuquerque, NM, visit http://www.cs.sandia.gov/CSRI. From bazara at sandia.gov Fri Aug 16 11:54:46 2002 From: bazara at sandia.gov (Zaragoza, Barbara) Date: Mon Oct 23 09:14:12 2006 Subject: [CSRI/CSMR Seminars] Reminder - CSRI Seminar Speaker - Todd Munson Message-ID: Computational Sciences and Mathematics Research (CSMR) Presents A Study in Support Vector Machines Todd S. Munson Argonne National Laboratory Date: Monday, August 19, 2002, 10 a.m. (PST) Location: Bldg. 921, Rm. 137(Sandia-CA)/Building 980, Rm. 95 (Sandia-NM) ABSTRACT: We discuss interior-point and semismooth methods for solving quadratic programming problems with a small number of linear constraints where the quadratic term consists of a low-rank update to a positive semi-definite matrix. Several formulations of the support vector machine, a technique employed by the machine learning community for supervised learning, fit into this category. A related example is the Huber regression problem, which can also be posed as a quadratic program with the desired properties. Support vector machines can be used, for example, when determining whether a tumor is malignant or benign. An interesting feature of the problems we consider is the volume of data, which can lead to quadratic programs with between 5 and 100 million variables and, if written explicitly, a dense $Q$ matrix. The implementations of the two algorithms use linear algebra specialized for the support vector machine application. For the targeted massive problems, all data is stored out-of-core and we overlap computation and I/O to reduce overhead. Results are reported for several linear support vector machine formulations demonstrating that the algorithms developed are reliable and scalable. ABOUT THE SPEAKER: Todd Munson works at Argonne National Laboratories in the Mathematics and Computer Science Division. His primary research focus is on algorithms and applications of complementarity. He has worked on two generalized Newton methods for solving these problems, one based on the Fischer-Burmeister reformulation and the other on the normal map reformulation. Each of these reformulations results in a nonsmooth system of equations to be solved. Implementations of these methods are available in the SEMI and PATH codes. Todd's recent work has been on a project to develop methods for solving optimization problems governed by partial differential equations. These are large nonlinear programming problems where parallel algorithms are needed. This work is part of the TOPS center. Todd received his Ph.D. in Computer Science from the University of Wisconsin in 2000 and has been a postdoctoral researcher at Argonne since then. Contact: Tamara Kolda (8950), (925) 294-4769, tgkolda@sandia.gov This seminar series is hosted by the CSMR Department at Sandia National Labs in Livermore, CA. For more information on upcoming events in The CSMR Department, visit http://csmr.ca.sandia.gov/news.html. For more information on The Computer Science Research Institute (CSRI) at Sandia National Labs in Albuquerque, NM, visit http://www.cs.sandia.gov/CSRI. From bazara at sandia.gov Tue Aug 20 15:35:12 2002 From: bazara at sandia.gov (Zaragoza, Barbara) Date: Mon Oct 23 09:14:12 2006 Subject: [CSRI/CSMR Seminars] Reminder: CSRI Speaker Series - Anne Greenbaum Message-ID: The Computer Science Research Institute (CSRI) Presents Theory and Applications of the Polynomial Numerical Hull Professor Anne Greenbaum University of Washington Math Department Date: Thursday, August 22, 2002 - 1:00 p.m. (PST) Location: Bldg. 921, Rm. 137(Sandia-CA) / Bldg. 980, Rm. 24 (Sandia-NM) ABSTRACT: The asymptotic behavior of a matrix or linear operator is governed by its eigenvalues, but, in general, the transient behavior is not. Yet this transient behavior is often important in physical applications such as convection and fluid flow and in numerical algorithms such as finite difference schemes and iterative methods for solving linear systems. In this talk we consider sets associated with a matrix $A$ that are designed to give more information than the spectrum alone can provide about this transient behavior. Specifically, we discuss the {\em polynomial numerical hull of degree $k$}, which is defined as the set of points $z$ in the complex plane for which $\| p(A) \| \geq | p(z) |$ for all polynomials $p$ of degree $k$ or less. Geometrical properties and methods for computing these sets are discussed. As a sample application, we show how these sets can be used to predict cutoff phenomena in Markov chains, such as the much-publicized result that it takes seven riffle shuffles to randomize a deck of cards. ABOUT THE SPEAKER: Professor Anne Greenbaum is a member of the University of Washington, Mathematics Department since 1997. Prior to this position, she was a research professor at the Courant Institute of Mathematical Sciences and a Mathematician at LLNL. Professor Greenbaum's professional activities include being a member of the SIAM Council and SIAM Program Committee. She is the author of three books, the most recent one, "Iterative Methods for Solving Linear Systems"; she has also refereed numerous publications. Professor Greenbaum received both her Ph.D and Master's degrees from the University of California, Berkeley Contact: Victoria Howle, (8950), (925) 294-2204, vehowle@sandia.gov This seminar series is hosted by the CSMR Department at Sandia National Labs in Livermore, CA. For more information on upcoming events in The CSMR Department, visit http://csmr.ca.sandia.gov/news.html. For more information on The Computer Science Research Institute (CSRI) at Sandia National Labs in Albuquerque, NM, visit http://www.cs.sandia.gov/CSRI.