Numerical Algorithms for Computing an Arbitrary Singular Value of a Tensor Sum
We consider computing an arbitrary singular value of a tensor sum: <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>T</mi><mo>:</mo><mo>=</mo><msub><mi>I&...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-08-01
|
| Series: | Axioms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2075-1680/10/3/211 |
| _version_ | 1797520167982333952 |
|---|---|
| author | Asuka Ohashi Tomohiro Sogabe |
| author_facet | Asuka Ohashi Tomohiro Sogabe |
| author_sort | Asuka Ohashi |
| collection | DOAJ |
| description | We consider computing an arbitrary singular value of a tensor sum: <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>T</mi><mo>:</mo><mo>=</mo><msub><mi>I</mi><mi>n</mi></msub><mo>⊗</mo><msub><mi>I</mi><mi>m</mi></msub><mo>⊗</mo><mi>A</mi><mo>+</mo><msub><mi>I</mi><mi>n</mi></msub><mo>⊗</mo><mi>B</mi><mo>⊗</mo><msub><mi>I</mi><mo>ℓ</mo></msub><mo>+</mo><mi>C</mi><mo>⊗</mo><msub><mi>I</mi><mi>m</mi></msub><mo>⊗</mo><msub><mi>I</mi><mo>ℓ</mo></msub><mo>∈</mo><msup><mi mathvariant="double-struck">R</mi><mrow><mo>ℓ</mo><mi>m</mi><mi>n</mi><mo>×</mo><mo>ℓ</mo><mi>m</mi><mi>n</mi></mrow></msup><mo>,</mo></mrow></semantics></math></inline-formula> where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>A</mi><mo>∈</mo><msup><mi mathvariant="double-struck">R</mi><mrow><mo>ℓ</mo><mo>×</mo><mo>ℓ</mo></mrow></msup></mrow></semantics></math></inline-formula>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>B</mi><mo>∈</mo><msup><mi mathvariant="double-struck">R</mi><mrow><mi>m</mi><mo>×</mo><mi>m</mi></mrow></msup></mrow></semantics></math></inline-formula>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>C</mi><mo>∈</mo><msup><mi mathvariant="double-struck">R</mi><mrow><mi>n</mi><mo>×</mo><mi>n</mi></mrow></msup></mrow></semantics></math></inline-formula>. We focus on the shift-and-invert Lanczos method, which solves a shift-and-invert eigenvalue problem of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mrow><mo stretchy="false">(</mo><msup><mi>T</mi><mi mathvariant="normal">T</mi></msup><mi>T</mi><mo>−</mo><msup><mover accent="true"><mi>σ</mi><mo>˜</mo></mover><mn>2</mn></msup><msub><mi>I</mi><mrow><mo>ℓ</mo><mi>m</mi><mi>n</mi></mrow></msub><mo stretchy="false">)</mo></mrow><mrow><mo>−</mo><mn>1</mn></mrow></msup></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mover accent="true"><mi>σ</mi><mo>˜</mo></mover></semantics></math></inline-formula> is set to a scalar value close to the desired singular value. The desired singular value is computed by the maximum eigenvalue of the eigenvalue problem. This shift-and-invert Lanczos method needs to solve large-scale linear systems with the coefficient matrix <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>T</mi><mi mathvariant="normal">T</mi></msup><mi>T</mi><mo>−</mo><msup><mover accent="true"><mi>σ</mi><mo>˜</mo></mover><mn>2</mn></msup><msub><mi>I</mi><mrow><mo>ℓ</mo><mi>m</mi><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>. The preconditioned conjugate gradient (PCG) method is applied since the direct methods cannot be applied due to the nonzero structure of the coefficient matrix. However, it is difficult in terms of memory requirements to simply implement the shift-and-invert Lanczos and the PCG methods since the size of <i>T</i> grows rapidly by the sizes of <i>A</i>, <i>B</i>, and <i>C</i>. In this paper, we present the following two techniques: (1) efficient implementations of the shift-and-invert Lanczos method for the eigenvalue problem of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>T</mi><mi mathvariant="normal">T</mi></msup><mi>T</mi></mrow></semantics></math></inline-formula> and the PCG method for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>T</mi><mi mathvariant="normal">T</mi></msup><mi>T</mi><mo>−</mo><msup><mover accent="true"><mi>σ</mi><mo>˜</mo></mover><mn>2</mn></msup><msub><mi>I</mi><mrow><mo>ℓ</mo><mi>m</mi><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula> using three-dimensional arrays (third-order tensors) and the <i>n</i>-mode products, and (2) preconditioning matrices of the PCG method based on the eigenvalue and the Schur decomposition of <i>T</i>. Finally, we show the effectiveness of the proposed methods through numerical experiments. |
| first_indexed | 2024-03-10T07:53:01Z |
| format | Article |
| id | doaj.art-320c6597de624502941961345cb8fdf0 |
| institution | Directory Open Access Journal |
| issn | 2075-1680 |
| language | English |
| last_indexed | 2024-03-10T07:53:01Z |
| publishDate | 2021-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Axioms |
| spelling | doaj.art-320c6597de624502941961345cb8fdf02023-11-22T12:03:03ZengMDPI AGAxioms2075-16802021-08-0110321110.3390/axioms10030211Numerical Algorithms for Computing an Arbitrary Singular Value of a Tensor SumAsuka Ohashi0Tomohiro Sogabe1National Institute of Technology, Kagawa College, Takuma Campus, Mitoyo 769-1192, JapanDepartment of Applied Physics, Nagoya University, Furo-cho, Chikusa-ku, Nagoya 464-8603, JapanWe consider computing an arbitrary singular value of a tensor sum: <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>T</mi><mo>:</mo><mo>=</mo><msub><mi>I</mi><mi>n</mi></msub><mo>⊗</mo><msub><mi>I</mi><mi>m</mi></msub><mo>⊗</mo><mi>A</mi><mo>+</mo><msub><mi>I</mi><mi>n</mi></msub><mo>⊗</mo><mi>B</mi><mo>⊗</mo><msub><mi>I</mi><mo>ℓ</mo></msub><mo>+</mo><mi>C</mi><mo>⊗</mo><msub><mi>I</mi><mi>m</mi></msub><mo>⊗</mo><msub><mi>I</mi><mo>ℓ</mo></msub><mo>∈</mo><msup><mi mathvariant="double-struck">R</mi><mrow><mo>ℓ</mo><mi>m</mi><mi>n</mi><mo>×</mo><mo>ℓ</mo><mi>m</mi><mi>n</mi></mrow></msup><mo>,</mo></mrow></semantics></math></inline-formula> where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>A</mi><mo>∈</mo><msup><mi mathvariant="double-struck">R</mi><mrow><mo>ℓ</mo><mo>×</mo><mo>ℓ</mo></mrow></msup></mrow></semantics></math></inline-formula>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>B</mi><mo>∈</mo><msup><mi mathvariant="double-struck">R</mi><mrow><mi>m</mi><mo>×</mo><mi>m</mi></mrow></msup></mrow></semantics></math></inline-formula>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>C</mi><mo>∈</mo><msup><mi mathvariant="double-struck">R</mi><mrow><mi>n</mi><mo>×</mo><mi>n</mi></mrow></msup></mrow></semantics></math></inline-formula>. We focus on the shift-and-invert Lanczos method, which solves a shift-and-invert eigenvalue problem of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mrow><mo stretchy="false">(</mo><msup><mi>T</mi><mi mathvariant="normal">T</mi></msup><mi>T</mi><mo>−</mo><msup><mover accent="true"><mi>σ</mi><mo>˜</mo></mover><mn>2</mn></msup><msub><mi>I</mi><mrow><mo>ℓ</mo><mi>m</mi><mi>n</mi></mrow></msub><mo stretchy="false">)</mo></mrow><mrow><mo>−</mo><mn>1</mn></mrow></msup></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mover accent="true"><mi>σ</mi><mo>˜</mo></mover></semantics></math></inline-formula> is set to a scalar value close to the desired singular value. The desired singular value is computed by the maximum eigenvalue of the eigenvalue problem. This shift-and-invert Lanczos method needs to solve large-scale linear systems with the coefficient matrix <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>T</mi><mi mathvariant="normal">T</mi></msup><mi>T</mi><mo>−</mo><msup><mover accent="true"><mi>σ</mi><mo>˜</mo></mover><mn>2</mn></msup><msub><mi>I</mi><mrow><mo>ℓ</mo><mi>m</mi><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula>. The preconditioned conjugate gradient (PCG) method is applied since the direct methods cannot be applied due to the nonzero structure of the coefficient matrix. However, it is difficult in terms of memory requirements to simply implement the shift-and-invert Lanczos and the PCG methods since the size of <i>T</i> grows rapidly by the sizes of <i>A</i>, <i>B</i>, and <i>C</i>. In this paper, we present the following two techniques: (1) efficient implementations of the shift-and-invert Lanczos method for the eigenvalue problem of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>T</mi><mi mathvariant="normal">T</mi></msup><mi>T</mi></mrow></semantics></math></inline-formula> and the PCG method for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>T</mi><mi mathvariant="normal">T</mi></msup><mi>T</mi><mo>−</mo><msup><mover accent="true"><mi>σ</mi><mo>˜</mo></mover><mn>2</mn></msup><msub><mi>I</mi><mrow><mo>ℓ</mo><mi>m</mi><mi>n</mi></mrow></msub></mrow></semantics></math></inline-formula> using three-dimensional arrays (third-order tensors) and the <i>n</i>-mode products, and (2) preconditioning matrices of the PCG method based on the eigenvalue and the Schur decomposition of <i>T</i>. Finally, we show the effectiveness of the proposed methods through numerical experiments.https://www.mdpi.com/2075-1680/10/3/211tensor sumsingular valueshift-and-invert Lanczos methodpreconditioned conjugate gradient method |
| spellingShingle | Asuka Ohashi Tomohiro Sogabe Numerical Algorithms for Computing an Arbitrary Singular Value of a Tensor Sum Axioms tensor sum singular value shift-and-invert Lanczos method preconditioned conjugate gradient method |
| title | Numerical Algorithms for Computing an Arbitrary Singular Value of a Tensor Sum |
| title_full | Numerical Algorithms for Computing an Arbitrary Singular Value of a Tensor Sum |
| title_fullStr | Numerical Algorithms for Computing an Arbitrary Singular Value of a Tensor Sum |
| title_full_unstemmed | Numerical Algorithms for Computing an Arbitrary Singular Value of a Tensor Sum |
| title_short | Numerical Algorithms for Computing an Arbitrary Singular Value of a Tensor Sum |
| title_sort | numerical algorithms for computing an arbitrary singular value of a tensor sum |
| topic | tensor sum singular value shift-and-invert Lanczos method preconditioned conjugate gradient method |
| url | https://www.mdpi.com/2075-1680/10/3/211 |
| work_keys_str_mv | AT asukaohashi numericalalgorithmsforcomputinganarbitrarysingularvalueofatensorsum AT tomohirosogabe numericalalgorithmsforcomputinganarbitrarysingularvalueofatensorsum |