header

トップ   差分 バックアップ リロード   一覧 単語検索 最終更新   ヘルプ   最終更新のRSS

第8回

日時: 2010年3月31日(水) 11:00 - 12:00

会場: 西8号館W棟8階W809号室

講演者: Marielba Rojas 氏 (Delft University of Technology, The Netherlands)

題目: Accelerating the LSTRS Algorithm

要旨:

The LSTRS algorithm presented in M. Rojas, S.A. Santos, and D.C. Sorensen. A new matrix-free method for the large-scale trust-region subproblem, SIAM J. Optim. 11(3): 611-646, 2000 is an iterative procedure for solving large-scale quadratic problems with one norm constraint, or trust-region subproblems. The method is based on a reformulation of the trust-region subproblem as a parametric eigenvalue problem. The main computation in LSTRS is the solution of a large, symmetric eigenvalue problem at each step.

The associated software (M. Rojas, S.A. Santos, and D.C. Sorensen. Algorithm 873: LSTRS: MATLAB software for large-scale trust-region subproblems and regularization, ACM Trans. Math. Software :11, 2008) offers several possibilities for the solution of the eigenproblems.

We present a brief description of the LSTRS algorithm with focus on the eigenvalue problems and their features. We describe recent work on improving the performance of LSTRS by means of efficient non-linear techniques for eigenvalue computations.

This is joint work with Joerg Lampe, Danny Sorensen, and Heinrich Voss.

第7回

日時: 2010年3月30日(火) 16:00 - 17:00

会場: 西8号館W棟10階W1008号室

講演者: Andrej Bogdanov 氏 (The Chinese University of Hong Kong)

題目: Adaptivity helps in testing bipartiteness

要旨:

We say a graph is epsilon-far from bipartite if it cannot be made bipartite even after removing an arbitrary set of epsilon n^2 of its edges. A test for bipartiteness (with distance parameter epsilon) is a randomized algorithm that, given access to the adjacency matrix of a large graph G, queries a small number of entries in the matrix, accepts if G is bipartite and rejects with high probability if G is epsilon-far from bipartite.

We give a new algorithm that tests bipartiteness in time O((1/epsilon)^{2-c}), where c > 0 is some universal constant. Our algorithm is inherently adaptive, as it is known that non-adaptive algorithms for testing bipartiteness require Omega((1/epsilon)^2) queries. (Based on joint work with Li Fan)

第6回

日時: 2010年3月29日(月) 16:30 - 17:30

会場: 西8号館W棟8階W809号室

講演者: 高橋 幸雄(数理・計算科学専攻)

第5回

日時: 2010年2月25日(木) 第1部 15:00 - 15:50, 第2部 16:00 - 17:00

会場: 東工大蔵前会館 手島精一記念会議室 (L, S)

講演者: 吉田 真紀 氏 (大阪大学)

題目: 第1部 多様性か否か - 安全性の形式的検証, 第2部 多様性か否か - 男女共同参画

要旨: 暗号理論のなかでも最近注目を集めている安全性の形式的検証に ついてお話しいただきます。また、大阪大学における女性研究者 支援の取り組みについてもご紹介いただきます。

なお、この講演は、男女共同参画推進センターとの共催であり、 文部科学省科学技術振興調整費「理工系女性研究者 プロモーションプログラム」の助成を受けています。

第4回

日時: 2010年1月15日(金) 16:30 - 17:30

会場: 西8号館W棟10階W1008号室

講演者: Wei-Ming Ni 氏(客員教授,University of Minnesota)

題目: ON THE DYNAMICS OF REACTION-DIFFUSION EQUATIONS AND THEIR SHADOW SYSTEMS

要旨: In this talk I will discuss and compare the following two aspects of the dynamics of 2x2 reaction-diffusion equations and their shadow systems: global existence/finite-time blow-up, and, stability properties of steady states. A well known activator-inhibitor system in morphogenesis developed by Alan Turing , and A. Gierer and H. Meinhardt, will be used as a primary example to illustrate the results.

第3回

日時: 2009年11月25日(水) 16:30 - 17:30

会場: 西8号館W棟10階W1008号室

講演者: Hans D. Mittelmann 氏 (Arizona State University)

題目: The Power of SDP Relaxations --- Computing Strong Bounds for QAPs and Graph Problems

要旨: As is well-known semidefinite relaxations of discrete optimization problems yield excellent bounds on their solutions. We present two examples from our recent research. The first addresses the quadratic assignment problem and a formulation is developed which yields the strongest lower bounds known for a number of large cases (up to dimension 256). It utilizes standard SDP software. With iterative SDP solvers still larger dimensions as they occur, for example, in communications, are within reach. The second area is the computation of bounds in graph problems, respectively in geometry. A strategy based on the Lovasz theta function is generalized to compute lower bounds for the chromatic number of graphs and upper bounds on the spherical kissing number utilizing SDP relaxations. Multiple precision SDP solvers are needed and improvements on known results for kissing numbers in dimensions up to 23 are obtained.

第2回

日時: 2009年6月3日(水) 13:30 - 14:30

会場: 西8号館W棟10階W1008号室

講演者: Joseph Maher 氏 (Oklahoma State University)

題目: Surfaces, groups and random walks.

要旨:

Every group has an intrinsic geometry associated with it, which can help us understand properties of the group, such as:

  • what does the group looks like on the large scale?
  • what properties does a generic group element have?

We will consider such questions for various families of groups, such as free groups, matrix groups, and groups arising from the study of surfaces, and we will mention some applications to 3-manifolds.

第1回

日時: 2009年5月7日(木) 13:20-

会場: 西8号館W棟8階W809号室

講演者: Karl Sigman 氏 (Columbia University)

題目: Brief introduction to Monte Carlo Simulation and its use for estimating the price of simple stock options (under the Binomial Lattice Model)