Top > Search of Japanese Patents > (In Japanese)固有値分解装置、及び固有値分解方法

(In Japanese)固有値分解装置、及び固有値分解方法 meetings

Patent code P09S000252
File No. 1396
Posted date Jan 12, 2010
Application number P2008-528725
Patent number P5017666
Date of filing Jan 31, 2007
Date of registration Jun 22, 2012
International application number JP2007051575
International publication number WO2008018188
Date of international filing Jan 31, 2007
Date of international publication Feb 14, 2008
Priority data
  • P2006-215660 (Aug 8, 2006) JP
Inventor
  • (In Japanese)中村 佳正
  • (In Japanese)坪井 洋明
  • (In Japanese)譽田 太朗
  • (In Japanese)岩▲崎▼ 雅史
  • (In Japanese)高田 雅美
Applicant
  • (In Japanese)国立大学法人京都大学
Title (In Japanese)固有値分解装置、及び固有値分解方法 meetings
Abstract (In Japanese)
【課題】
 高速・高精度であり、並列処理可能な固有値分解装置を提供する。
【解決手段】
 対称3重対角行列Tを2個の対称3重対角行列に分割する処理を繰り返し行う行列分割部14と、分割後の対称3重対角行列を固有値分解する固有値分解部15と、固有値分解部15によって固有値分解された固有値と、固有ベクトルからなる直交行列の一部の要素である行列要素とから、分割元の対称3重対角行列の固有値と、分割元の対称3重対角行列の行列要素とを算出する処理を、対称3重対角行列Tの固有値を算出するまで繰り返す固有値算出部17と、対称3重対角行列Tとその固有値とから、ツイスト分解法を用いて対称3重対角行列Tの固有ベクトルを算出する固有ベクトル算出部19と、を備える。
【選択図】
 図1
Outline of related art and contending technology (In Japanese)


固有値分解は、例えば、分子軌道法による化学計算、統計計算、情報検索等の非常に広い分野で利用されている。また、固有値分解の方法も知られている(例えば、非特許文献1参照)。
【非特許文献1】
J.J.M.Cuppen,「A divide and conquer method for the symmetric tridiagonal eigenproblem」、Numerische Mathematik,Vol.36、p.177-195、1981年

Field of industrial application (In Japanese)


本発明は、固有値分解を行う固有値分解装置等に関する。

Scope of claims (In Japanese)
【請求項1】
 
対称3重対角行列Tが記憶される対角行列記憶部と、
前記対角行列記憶部から前記対称3重対角行列Tを読み出し、当該対称3重対角行列Tを2個の対称3重対角行列に分割して前記対角行列記憶部に蓄積し、その対称3重対角行列を2個の対称3重対角行列に分割して前記対角行列記憶部に蓄積する処理を、分割後の各対称3重対角行列があらかじめ決められた大きさ以下となるまで繰り返す行列分割部と、
前記あらかじめ決められた大きさ以下の各対称3重対角行列の固有値と、当該各対称3重対角行列の固有ベクトルからなる直交行列の一部の要素である行列要素とが記憶される固有値分解記憶部と、
前記あらかじめ決められた大きさ以下の各対称3重対角行列を前記対角行列記憶部から読み出し、前記各対称3重対角行列に対して固有値分解を行い、前記各対称3重対角行列の固有値と、前記各対称3重対角行列の固有ベクトルからなる直交行列の行列要素とを少なくとも算出し、当該固有値と当該行列要素とを前記固有値分解記憶部に蓄積する固有値分解部と、
前記対称3重対角行列Tの固有値が記憶される固有値記憶部と、
各対称3重対角行列の固有値と、行列要素とを前記固有値分解記憶部から読み出し、前記固有値と、前記行列要素とから、分割元の対称3重対角行列の固有値と、分割元の対称3重対角行列の行列要素とを算出して前記固有値分解記憶部に蓄積し、その分割元の対称3重対角行列の固有値と、行列要素とを算出する処理を、対称3重対角行列Tの少なくとも1個の固有値を算出するまで繰り返し、前記対称3重対角行列Tの少なくとも1個の固有値を前記固有値記憶部に蓄積する固有値算出部と、
前記対称3重対角行列Tの固有ベクトルが記憶される固有ベクトル記憶部と、
前記対角行列記憶部から前記対称3重対角行列Tを読み出し、前記固有値記憶部から前記対称3重対角行列Tの固有値を読み出し、前記対称3重対角行列Tとその固有値とから、ツイスト分解法を用いて前記対称3重対角行列Tの少なくとも1個の固有ベクトルを算出して前記固有ベクトル記憶部に蓄積する固有ベクトル算出部と、を備えた固有値分解装置。

【請求項2】
 
前記固有ベクトル算出部は、qd型ツイスト分解法により固有ベクトルを算出する、請求項1記載の固有値分解装置。

【請求項3】
 
前記固有ベクトル算出部は、
前記固有値記憶部から前記対称3重対角行列Tの固有値を読み出し、当該固有値のいずれかが負の値である場合に、前記対角行列記憶部から前記対称3重対角行列Tを読み出し、当該対称3重対角行列Tの固有ベクトルを変化させることなく、当該対称3重対角行列Tのすべての固有値が正の値となるように、当該対称3重対角行列Tを正定値化し、正定値化した後の固有値を前記固有値記憶部に蓄積し、正定値化した後の対称3重対角行列Tを前記対角行列記憶部に蓄積する正定値化部と、
前記対角行列記憶部からすべての固有値が正の値である対称3重対角行列Tを読み出し、前記固有値記憶部から前記対称3重対角行列Tの正の値の固有値を読み出し、前記対称3重対角行列Tの各要素に関してqd型変換を行うことによって、前記対称3重対角行列Tを上2重対角行列B(+1)及び下2重対角行列B(-1)にコレスキー分解するコレスキー分解部と、
前記上2重対角行列B(+1)及び下2重対角行列B(-1)の各要素と、前記対称3重対角行列Tの正の値の固有値とを用いて固有ベクトルを算出して前記固有ベクトル記憶部に蓄積するベクトル算出部と、を備えた、請求項2記載の固有値分解装置。

【請求項4】
 
前記固有ベクトル算出部は、LV型ツイスト分解法により固有ベクトルを算出する、請求項1記載の固有値分解装置。

【請求項5】
 
前記固有ベクトル算出部は、
前記対角行列記憶部から前記対称3重対角行列Tを読み出し、前記固有値記憶部から前記対称3重対角行列Tの固有値を読み出し、前記対称3重対角行列Tの各要素に関してミウラ変換、dLVv型変換、逆ミウラ変換を行うことによって、前記対称3重対角行列Tを上2重対角行列B(+1)及び下2重対角行列B(-1)にコレスキー分解するコレスキー分解部と、
前記上2重対角行列B(+1)及び下2重対角行列B(-1)の各要素と、前記対称3重対角行列Tの固有値とを用いて固有ベクトルを算出して前記固有ベクトル記憶部に蓄積するベクトル算出部と、を備えた、請求項4記載の固有値分解装置。

【請求項6】
 
前記コレスキー分解部は、複数のコレスキー分解手段を備え、
前記複数のコレスキー分解手段が、前記対称3重対角行列Tをコレスキー分解する処理を並列実行する、請求項3または請求項5記載の固有値分解装置。

【請求項7】
 
前記ベクトル算出部は、複数のベクトル算出手段を備え、
前記複数のベクトル算出手段が、固有ベクトルを算出する処理を並列実行する、請求項3、請求項5または請求項6記載の固有値分解装置。

【請求項8】
 
前記固有値算出部は、複数の固有値算出手段を備え、
前記複数の固有値算出手段が、分割元の対称3重対角行列の固有値と、行列要素とを算出する処理を並列実行する、請求項1から請求項7のいずれか記載の固有値分解装置。

【請求項9】
 
前記固有値分解部は、複数の固有値分解手段を備え、
前記複数の固有値分解手段が、対称3重対角行列に対して固有値分解を行う処理を並列実行する、請求項1から請求項8のいずれか記載の固有値分解装置。

【請求項10】
 
対称行列Aが記憶される行列記憶部と、
前記対称行列Aを前記行列記憶部から読み出し、前記対称行列Aを3重対角化した前記対称3重対角行列Tを算出して前記対角行列記憶部に蓄積する対角化部と、をさらに備えた請求項1から請求項9のいずれか記載の固有値分解装置。

【請求項11】
 
前記行列分割部は、対称3重対角行列を略半分の2個の対称3重対角行列に分割する、請求項1から請求項10のいずれか記載の固有値分解装置。

【請求項12】
 
前記固有値算出部は、対称3重対角行列Tの全ての固有値を算出する、請求項1から請求項11のいずれか記載の固有値分解装置。

【請求項13】
 
前記固有ベクトル算出部は、対称3重対角行列Tの全ての固有ベクトルを算出する、請求項12記載の固有値分解装置。

【請求項14】
 
前記対称行列Aは、顔画像データを示すベクトルの平均から算出された共分散行列である、請求項10記載の固有値分解装置。

【請求項15】
 
対称3重対角行列Tが記憶される対角行列記憶部と、行列分割部と、固有値分解部と、前記固有値分解部によって固有値分解された固有値と固有ベクトルからなる直交行列の一部の要素である行列要素とが記憶される固有値分解記憶部と、前記対称3重対角行列Tの固有値が記憶される固有値記憶部と、固有値算出部と、前記対称3重対角行列Tの固有ベクトルが記憶される固有ベクトル記憶部と、固有ベクトル算出部とを備えた固有値分解装置で用いられる固有値分解方法であって、
前記行列分割部が、前記対角行列記憶部から前記対称3重対角行列Tを読み出し、当該対称3重対角行列Tを2個の対称3重対角行列に分割して前記対角行列記憶部に蓄積し、その対称3重対角行列を2個の対称3重対角行列に分割して前記対角行列記憶部に蓄積する処理を、分割後の各対称3重対角行列があらかじめ決められた大きさ以下となるまで繰り返す行列分割ステップと、
前記固有値分解部が、前記あらかじめ決められた大きさ以下の各対称3重対角行列を前記対角行列記憶部から読み出し、前記各対称3重対角行列に対して固有値分解を行い、前記各対称3重対角行列の固有値と、前記各対称3重対角行列の固有ベクトルからなる直交行列の行列要素とを少なくとも算出し、当該固有値と当該行列要素とを前記固有値分解記憶部に蓄積する固有値分解ステップと、
前記固有値算出部が、各対称3重対角行列の固有値と、行列要素とを前記固有値分解記憶部から読み出し、前記固有値と、前記行列要素とから、分割元の対称3重対角行列の固有値と、分割元の対称3重対角行列の行列要素とを算出して前記固有値分解記憶部に蓄積し、その分割元の対称3重対角行列の固有値と、行列要素とを算出する処理を、対称3重対角行列Tの少なくとも1個の固有値を算出するまで繰り返し、前記対称3重対角行列Tの少なくとも1個の固有値を前記固有値記憶部に蓄積する固有値算出ステップと、
前記固有ベクトル算出部が、前記対角行列記憶部から前記対称3重対角行列Tを読み出し、前記固有値記憶部から前記対称3重対角行列Tの固有値を読み出し、前記対称3重対角行列Tとその固有値とから、ツイスト分解法を用いて前記対称3重対角行列Tの少なくとも1個の固有ベクトルを算出して前記固有ベクトル記憶部に蓄積する固有ベクトル算出ステップと、を備えた固有値分解方法。

【請求項16】
 
コンピュータに、
対称3重対角行列Tが記憶される対角行列記憶部から前記対称3重対角行列Tを読み出し、当該対称3重対角行列Tを2個の対称3重対角行列に分割して前記対角行列記憶部に蓄積し、その対称3重対角行列を2個の対称3重対角行列に分割して前記対角行列記憶部に蓄積する処理を、分割後の各対称3重対角行列があらかじめ決められた大きさ以下となるまで繰り返す行列分割ステップと、
前記あらかじめ決められた大きさ以下の各対称3重対角行列を前記対角行列記憶部から読み出し、前記各対称3重対角行列に対して固有値分解を行い、前記各対称3重対角行列の固有値と、前記各対称3重対角行列の固有ベクトルからなる直交行列の行列要素とを少なくとも算出し、当該固有値と当該行列要素とを固有値分解記憶部に蓄積する固有値分解ステップと、
各対称3重対角行列の固有値と、行列要素とを前記固有値分解記憶部から読み出し、前記固有値と、前記行列要素とから、分割元の対称3重対角行列の固有値と、分割元の対称3重対角行列の行列要素とを算出して前記固有値分解記憶部に蓄積し、その分割元の対称3重対角行列の固有値と、行列要素とを算出する処理を、対称3重対角行列Tの少なくとも1個の固有値を算出するまで繰り返し、前記対称3重対角行列Tの少なくとも1個の固有値を固有値記憶部に蓄積する固有値算出ステップと、
前記対角行列記憶部から前記対称3重対角行列Tを読み出し、前記固有値記憶部から前記対称3重対角行列Tの固有値を読み出し、前記対称3重対角行列Tとその固有値とから、ツイスト分解法を用いて前記対称3重対角行列Tの少なくとも1個の固有ベクトルを算出して固有ベクトル記憶部に蓄積する固有ベクトル算出ステップと、を実行させるためのプログラム。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2008528725thum.jpg
State of application right Registered
Please contact us by e-mail or facsimile if you have any interests on this patent. Thanks.


PAGE TOP

close
close
close
close
close
close
close