`
`Aldana et al.
`In re Patent of:
`8,416,862
`
`U.S. Pat. No.:
`April 9, 2013
`Issue Date:
`Appl. Serial No.: 11/237,341
`Filing Date:
`September 28, 2005
`Title:
`EFFICIENT FEEDBACK OF CHANNEL INFORMATION IN
`A CLOSED LOOP BEAMFORMING WIRELESS
`COMMUNICATION SYSTEM
`
`Attorney Docket No.: 50095-0050IP1
`
`Declaration of Jacob Robert Munford
`
`1
`
`OnePlus Ex. 1021.0001
`IPR2022-00048
`
`
`
`1. My name is Jacob Robert Munford. I am over the age of 18, have personal
`
`knowledge of the facts set forth herein, and am competent to testify to the
`
`same.
`
`2. I earned a Master of Library and Information Science (MLIS) from the
`
`University of Wisconsin-Milwaukee in 2009. I have over ten years of
`
`experience in the library/information science field. Beginning in 2004, I
`
`have served in various positions in the public library sector including
`
`Assistant Librarian, Youth Services Librarian and Library Director. I have
`
`attached my Curriculum Vitae as Appendix A.
`
`3. During my career in the library profession, I have been responsible for
`
`materials acquisition for multiple libraries. In that position, I have cataloged,
`
`purchased and processed incoming library works. That includes purchasing
`
`materials directly from vendors, recording publishing data from the material
`
`in question, creating detailed material records for library catalogs and
`
`physically preparing that material for circulation. In addition to my
`
`experience in acquisitions, I was also responsible for analyzing large
`
`collections of library materials, tailoring library records for optimal catalog
`
`2
`
`OnePlus Ex. 1021.0002
`IPR2022-00048
`
`
`
`search performance and creating lending agreements between libraries
`
`during my time as a Library Director.
`
`4. I am fully familiar with the catalog record creation process in the library
`
`sector. In preparing a material for public availability, a library catalog record
`
`describing that material would be created. These records are typically
`
`written in Machine Readable Catalog (herein referred to as “MARC”) code
`
`and contain information such as a physical description of the material,
`
`metadata from the material’s publisher, and date of library acquisition. In
`
`particular, the 008 field of the MARC record is reserved for denoting the
`
`date of creation of the library record itself. As this typically occurs during
`
`the process of preparing materials for public access, it is my experience that
`
`an item’s MARC record indicates the date of an item’s public availability.
`
`5. I have reviewed Exhibit EX1008, an article by B. Yang and J.F. Bohme
`
`entitled “Reducing The Computations of the Singular Value Decomposition
`
`Array Given By Brent and Luk” (hereto referred to as ‘Yang’) as presented
`
`in SIAM Journal On Matrix Analysis and Applications Volume 12, Issue 4.
`
`6. Attached hereto as YA01 is a true and correct copy of the spine, publication
`
`data, title page and complete ‘Yang’ from SIAM Journal On Matrix Analysis
`
`3
`
`OnePlus Ex. 1021.0003
`IPR2022-00048
`
`
`
`and Applications from the University of Pittsburgh library. In comparing
`
`YA01 to Exhibit EX1008, it is my determination that Exhibit EX1008 is a
`
`true and correct copy of ‘Yang’.
`
`7. Attached hereto as YA02 is a true and correct copy of the MARC record
`
`describing SIAM Journal On Matrix Analysis and Application from the
`
`University of Pittsburgh’s library. I secured this record myself from the
`
`library’s online catalog. The 008 field of this MARC record indicates SIAM
`
`Journal On Matrix Analysis and Application was first cataloged by the
`
`University of Pittsburgh library as of September 9, 1987. The item holdings
`
`indicate this journal was held in perpetuity since September 1987. This item
`
`record also indicates the library’s collection includes the Volume 12, Issue 4
`
`publication of SIAM Journal On Matrix Analysis and Application containing
`
`“Yang”.
`
`8. The date stamp on page 4 of YA01 indicates this journal was processed by
`
`library staff as of November 1991. Considering this information in concert
`
`with the record data from YA02, it is my determination that the Volume 12,
`
`Issue 4 edition of SIAM Journal On Matrix Analysis and Application was
`
`made available and accessible to the public by the University of Pittsburgh
`
`library shortly after initial publication and certainly no later than November
`
`4
`
`OnePlus Ex. 1021.0004
`IPR2022-00048
`
`
`
`1991. Based on journal availability, it is my determination that ‘Yang’ was
`
`made available and accessible to the public shortly after initial publication
`
`via SIAM Journal On Matrix Analysis and Application.
`
`9. I have been retained on behalf of the Petitioner to provide assistance in the
`
`above-illustrated matter in establishing the authenticity and public
`
`availability of the documents discussed in this declaration. I am being
`
`compensated for my services in this matter at the rate of $100.00 per hour
`
`plus reasonable expenses. My statements are objective, and my
`
`compensation does not depend on the outcome of this matter.
`
`10. I declare under penalty of perjury that the foregoing is true and correct. I
`
`hereby declare that all statements made herein of my own knowledge are
`
`true and that all statements made on information and belief are believed to
`
`be true; and further that these statements were made the knowledge that
`
`willful false statements and the like so made are punishable by fine or
`
`imprisonment, or both, under Section 1001 of Title 18 of the United States
`
`Code.
`
`5
`
`OnePlus Ex. 1021.0005
`IPR2022-00048
`
`
`
`Dated: 9/30/2021
`
`Jacob Robert Munford
`
`6
`
`OnePlus Ex. 1021.0006
`IPR2022-00048
`
`
`
`APPENDIX A
`APPENDIX A
`
`7
`
`OnePlus Ex. 1021.0007
`IPR2022-00048
`
`7
`
`OnePlus Ex. 1021.0007
`IPR2022-00048
`
`
`
`J. Munford
`Curriculum Vitae
`
`Education
`
`University of Wisconsin-Milwaukee - MS, Library & Information Science, 2009
`Milwaukee, WI
`
`● Coursework included cataloging, metadata, data analysis, library systems,
`management strategies and collection development.
`● Specialized in library advocacy, cataloging and public administration.
`
`Grand Valley State University - BA, English Language & Literature, 2008
`Allendale, MI
`
`● Coursework included linguistics, documentation and literary analysis.
`● Minor in political science with a focus in local-level economics and
`government.
`
`Professional Experience
`
`Researcher / Expert Witness, October 2017 – present
`Freelance ● Pittsburgh, Pennsylvania & Grand Rapids, Michigan
`
`● Material authentication and public accessibility determination.
`Declarations of authenticity and/or public accessibility provided upon
`research completion. Experienced with appeals and deposition process.
`
`● Research provided on topics of public library operations, material
`publication history, digital database services and legacy web resources.
`
`● Past clients include Alston & Bird, Arnold & Porter, Baker Botts, Fish &
`Richardson, Erise IP, Irell & Manella, O'Melveny & Myers, Perkins-Coie,
`Pillsbury Winthrop Shaw Pittman and Slayden Grubert Beard.
`
`Library Director, February 2013 - March 2015
`Dowagiac District Library ● Dowagiac, Michigan
`
`● Executive administrator of the Dowagiac District Library. Located in
`
`8
`
`OnePlus Ex. 1021.0008
`IPR2022-00048
`
`
`
`Southwest Michigan, this library has a service area of 13,000, an annual
`operating budget of over $400,000 and total assets of approximately
`$1,300,000.
`
`● Developed careful budgeting guidelines to produce a 15% surplus during
`the 2013-2014 & 2014-2015 fiscal years while being audited.
`
`● Using this budget surplus, oversaw significant library investments
`including the purchase of property for a future building site, demolition of
`existing buildings and building renovation projects on the current facility.
`
`● Led the organization and digitization of the library's archival records.
`
`● Served as the public representative for the library, developing business
`relationships with local school, museum and tribal government entities.
`
`● Developed an objective-based analysis system for measuring library
`services - including a full collection analysis of the library's 50,000+
`circulating items and their records.
`
`November 2010 - January 2013
`Librarian & Branch Manager, Anchorage Public Library ● Anchorage, Alaska
`
`● Headed the 2013 Anchorage Reads community reading campaign
`including event planning, staging public performances and creating
`marketing materials for mass distribution.
`
`● Co-led the social media department of the library's marketing team,
`drafting social media guidelines, creating original content and instituting
`long-term planning via content calendars.
`
`● Developed business relationships with The Boys & Girls Club, Anchorage
`School District and the US Army to establish summer reading programs for
`children.
`
`June 2004 - September 2005, September 2006 - October 2013
`Library Assistant, Hart Area Public Library
`Hart, MI
`
`● Responsible for verifying imported MARC records and original MARC
`
`9
`
`OnePlus Ex. 1021.0009
`IPR2022-00048
`
`
`
`cataloging for the local-level collection as well as the Michigan Electronic
`Library.
`
`● Handled OCLC Worldcat interlibrary loan requests & fulfillment via
`ongoing communication with lending libraries.
`
`Professional Involvement
`
`Alaska Library Association - Anchorage Chapter
`● Treasurer, 2012
`
`Library Of Michigan
`● Level VII Certification, 2008
`● Level II Certification, 2013
`
`Michigan Library Association Annual Conference 2014
`● New Directors Conference Panel Member
`
`Southwest Michigan Library Cooperative
`● Represented the Dowagiac District Library, 2013-2015
`
`Professional Development
`
`Library Of Michigan Beginning Workshop, May 2008
`Petoskey, MI
`● Received training in cataloging, local history, collection management,
`children’s literacy and reference service.
`
`Public Library Association Intensive Library Management Training, October 2011
`Nashville, TN
`● Attended a five-day workshop focused on strategic planning, staff
`management, statistical analysis, collections and cataloging theory.
`
`Alaska Library Association Annual Conference 2012 - Fairbanks, February 2012
`Fairbanks, AK
`● Attended seminars on EBSCO advanced search methods, budgeting,
`cataloging, database usage and marketing.
`
`10
`
`OnePlus Ex. 1021.0010
`IPR2022-00048
`
`
`
`Depositions
`
`2019 ● Fish & Richardson
`IPR Petitions of 865 Patent, Apple v. Qualcomm (IPR2018-001281 /
`39521-00421IP & IPR2018-01282 / 39521-00421IP2)
`
`2019 ● Erise IP
`Implicit, LLC v. Netscout Systems, Inc (Civil Action No. 2:18-cv-53-JRG)
`
`2019 ● Perkins-Coie
`Adobe Inc. v. RAH Color Technologies LLC (Cases IPR2019-00627,
`IPR2019-00628, IPR2019-00629 and IPR2019-00646)
`
`2020 ● O’Melveny & Myers
`Maxell, Ltd. v. Apple Inc. (Case 5:19-cv-00036-RWS)
`
`2021 ● Pillsbury Winthrop Shaw Pittman LLP
`Intel v. SRC (Case IPR2020-1449)
`
`Limited Case History & Potential Conflicts
`
`Alston & Bird
`● Nokia (v. Neptune Subsea, Xtera)
`
`Arnold & Porter
`● Ivantis (v. Glaukos)
`
`Erise I.P.
`● Apple
`v. Future Link Systems (IPRs 6317804, 6622108, 6807505, and
`7917680)
`v. INVT
`v. Navblazer LLC (Case No. IPR2020-01253)
`
`11
`
`OnePlus Ex. 1021.0011
`IPR2022-00048
`
`
`
`v. Qualcomm (IPR2018-001281, 39521-00421IP, IPR2018-01282,
`39521-00421IP2)
`v. Quest Nettech Corp, Wynn Technologies (Case No. IPR2019-
`00XXX, RE. Patent Re38137)
`
`● Fanduel (v CGT)
`
`● Garmin (v. Phillips North America LLC, Case No. 2:19-cv-6301-AB-KS
`Central District of California)
`
`● Netscout
`v. Longhorn HD LLC)
`v. Implicit, LLC (Civil Action No. 2:18-cv-53-JRG)
`● Sony Interactive Entertainment LLC
`v. Bot M8 LLC
`v. Infernal Technology LLC
`● Unified Patents (v GE Video Compression, Civil Action No. 2:19-cv-248)
`
`Fish & Richardson
`● Apple
`v. LBS Innovations
`v. Masimo (IPR 50095-0012IP1, 50095-0012IP2, 50095-0013IP1,
`50095-0013IP2, 50095-0006IP1)
`v. Neonode
`v. Qualcomm (IPR2018-001281, 39521-00421IP, IPR2018-01282,
`39521-00421IP2)
`
`● Dish Network
`v. Realtime Adaptive Streaming, Case No 1:17-CV-02097-RBJ)
`
`12
`
`OnePlus Ex. 1021.0012
`IPR2022-00048
`
`
`
`v. TQ Delta LLC
`
`● Huawei (IPR 76933211)
`
`● Kianxis
`
`● LG Electronics (v. Bell Northern Research LLC, Case No. 3:18-cv-2864-
`CAB-BLM)
`
`● Metaswitch
`
`● MLC Intellectual Property (v. MicronTech, Case No. 3:14-cv-03657-SI)
`
`● Realtek Semiconductor
`
`● Quectel
`
`● Samsung (v. Bell Northern Research, Civil Action No. 2:19-cv-00286-
`JRG)
`
`● Texas Instruments
`
`Irell & Manella
`● Curium
`
`O’Melveny & Myers
`● Apple (v. Maxell, Case 5:19-cv-00036-RWS)
`
`Perkins-Coie
`● TCL Industries (v. Koninklijke Philips NV, PTAB Case Nos. IPR2021-
`00495, IPR2021-00496, and IPR2021-00497)
`
`Pillsbury Winthrop Shaw Pittman
`● Intel (v. FG SRC LLC, Case No. 6:20-cv-00315 W.D. Tex)
`
`13
`
`OnePlus Ex. 1021.0013
`IPR2022-00048
`
`
`
`YA01
`YAOI
`
`14
`
`OnePlus Ex. 1021.0014
`IPR2022-00048
`
`14
`
`OnePlus Ex. 1021.0014
`IPR2022-00048
`
`
`
`IM)
`
`5 050 777 956 nePlus
`
`1021.0015
`Ex.
`IPR2022-00048
`
`15
`
`OnePlus Ex. 1021.0015
`IPR2022-00048
`
`
`
`STAM
`BUa)
`Meee
`ANALYSIS AND
`
`APPLICATIONS OnePlus Ex. 1021.0016
`
`IPR2022-00048
`
`16
`
`OnePlus Ex. 1021.0016
`IPR2022-00048
`
`
`
`R@8-M16-S24-Te6
`31735050777956
`AACAAA
`Hillman Gr.Fl. Lending
`Request IDi 432140
`Pull Date: 2619-87723 113032
`Call No.
`
`Title? SIAM journal on matrix analysi
`
`RED
`
`MUNFORD, JACOB R
`ULSertsyB
`2L666268035853sS
`Req. Date: 2019/07/23 10:07:43
`
`Do Not Remove This Wrapper
`
`
`
`University of Pittsburgh
`University Library System
`Storage
`Facility
`
`DO NOT
`CIRCULATE
`DO NOT
`
`
`
`17
`
`.0017
`Ex.
`nePlius
`IPR2022-00048
`
`17
`
`OnePlus Ex. 1021.0017
`IPR2022-00048
`
`
`
`
`
`OnePlus Ex. 1021.0018
`IPR2022-00048
`
`18
`
`OnePlus Ex. 1021.0018
`IPR2022-00048
`
`
`
`SIAM JOURNAL ON
`
`Matrix Analysis
`and Applications
`
`VOLUME 12
`
`
`Managing Editor
`Associate
`Managing Editor
`Editorial Board
`
`G. H. Golub
`
`R. J. Plemmons
`
`T. Ando
`A. Berman
`R. Brualdl
`J. Bunch
`A. Bunse-Gerstner
`P. J. Courtois
`G. Cybenko
`B. N. Datta
`Y. Genin
`J. R. Gilbert
`L. J. Gleser
`M. Goldberg
`W.B. Gragg
`
`A. Greenbaum
`. Gutknecht
`. Hammarling
`. J. Higham
`A. Horn
`. Kagstrém
`. Kautsky
`. Lancaster
`W. H. Liu
`T. Luk
`. A. Manteuffel
`S. Maybee
`. L. Merris
`
`DOANVEDDZMES
`
`C. Meyer
`N. K. Nichols
`|. Olkin
`J. S. Pang
`U. G. Rothblum
`K. Sigmon
`G. Strang
`P. van Dooren
`C. Van Loan
`R. S. Varga
`A. Watson
`H. Weinberger
`
`eeeeeeeeSSSFSFSFSSSSeeeeeeSSSSSSSSsSS
`Copyright 1991 by the Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania.
`
`19
`
`OnePlus Ex. 1021.0019
`IPR2022-00048
`
`19
`
`OnePlus Ex. 1021.0019
`IPR2022-00048
`
`
`
`
`
`AN
`JOURNAL ON
`
`Matrix Analysis
`and Applications
`
`OCTOBER 1991
`Volume 12, Number 4
`
`
`Managing Editor
`Associate
`Managing Editor
`
`Editorial Board
`
`G. H. Golub
`
`R. J. Plemmons
`
`1. Ando
`A. Berman
`R. Brualdi
`J. Bunch
`A. Bunse-Gerstner
`P. J. Courtois
`G. Cybenko
`B. N. Datta
`Y. Genin
`J. R. Gilbert
`L. J. Gleser
`M. Goldberg
`W. B. Gragg
`
`A. Greenbaum
`M. Gutknecht
`S. Hammarling
`N. J. Higham
`R. A. Horn
`B. Kagstr6m
`J. Kautsky
`P. Lancaster
`J. W. H. Liu
`F. T. Luk
`T. A. Manteuffel
`J. S. Maybee
`R. L. Merris
`
`C. Meyer
`N. K. Nichols
`|. Olkin
`J. S. Pang
`U. G. Rothblum
`K. Sigmon
`G. Strang
`P. van Dooren
`C. Van Loan
`R. S. Varga
`A. Watson
`H. Weinberger
`
`nn
`
`Publisher: Vickie H. Kearn. Production Manager: J. Corey Gray. Managing Editor: Tricia Manning. Senior
`Production Editor: Crystal G. Norris. Copy Editor: Beth Gallagher. Editorial Assistant: David Livewell. Pro-
`duction Coordinator: Nancy H. Abbott. Reprints Coordinator: Jill M. Davis.
`
`SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS(ISSN 0895-4798)is published quarterly in January,
`April, July, and October by the Society for Industrial and Applied Mathematics, 3600 University City Science
`Center, Philadelphia, PA 19104-2688. Second-class postage paid at Philadelphia, Pennsylvania and additional
`mailing offices. POSTMASTER: Send address change to S/AM Journal on Matrix Analysis and Applications,
`3600 University City Science Center, Philadelphia, PA 19104-2688.
`
`Subscriptions: Annual subscriptionlist price: $130.00 (domestic), $155.00 (overseas); annualindividual member
`subscription price: $40.00 (domestic), $43.00 (overseas). Subscriptions are available on a calendar-year basis
`only. Send orders to Customer Service, SIAM, 3600 University City Science Center, Philadelphia, PA 19104-2688.
`In Japan send orders to USACO Corporation, 13-12, Shimbashi, 1-chome, Minato-ku, Tokyo 105, tel. 03(502)-
`6471. All back volumesare available; prices will be provided on request. Manuscript Submissions:See Instructions
`to Authors on pageiv of this journal. Advertising: Accepted forall publications. Inquiries should be directed to
`the Marketing Manager, SIAM Publications, 3600 University City Science Center, Philadelphia, PA 19104-2688.
`Authorization to photocopyitemsfor internal and personaluse,or the internal use of specific clients,is granted
`by the Society for Industrial and Applied Mathematicsforlibraries and other users registered with the Copyright
`Clearance Center (CCC) Transactional Reporting Service provided that the base fee of $1.50 per copy plus $0.10
`per pageis paid directly to CCC, 21 Congress Street, Salem, Massachusetts 01970.
`
`TAPSCO,Inc., Akron, Pennsylvania, compositor; Lancaster Press, Lancaster, Pennsylvania,printer.
`The SIAM Journal on Matrix Analysis and Applications is a continuation of the SIAM Journal on Algebraic and
`Discrete Methods (ISSN 0196-5212).
`
`Copyright 1991 by the Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania.
`Siamisa registered trademark.
`
`ae
`
`20
`
`b020
`OnePlus Ex.
`IPR2022-00048
`
`20
`
`OnePlus Ex. 1021.0020
`IPR2022-00048
`
`
`
`SIAM J. MATRIX ANAL. APPL.
`Vol. 12, No. 4, pp. 713-725, October 1991
`
`© 1991 Society for Industrial and Applied Mathematics
`009
`
`REDUCING THE COMPUTATIONS OF THE SINGULAR VALUE
`DECOMPOSITION ARRAY GIVEN BY BRENT AND LUK*
`
`B. YANG+ AnD J. F. BOHME+
`
`Abstract. A new,efficient, two-plane rotation (TPR) method for computing two-sided rotations involved
`insingular value decomposition (SVD) is presented. It is shown that a two-sided rotation can be evaluated by
`only two plane rotations and a few additions. This leads to significantly reduced computations. Moreover,if
`coordinate rotation digital computer (CORDIC) processors are usedfor realizing the processing elements(PEs)
`of the SVD array given by Brent and Luk, the computational overhead of the diagonal PEs due to angle
`calculations can be avoided. The resulting SVD array has a homogeneousstructure with identical diagonal and
`off-diagonal PEs. Similar results can also be obtained if the TPR method is applied to Luk’s triangular SVD
`array and to Stewart’s Schur decomposition array.
`
`Key words. singular value decomposition, systolic arrays, CORDIC, two-sidedrotations, VLSI
`
`AMS(MOS)subjectclassification. 15A18
`
`
`
`
`
`
`
`
`
`
`
`
`* Received by the editors September 28, 1989; accepted for publication (in revised form) August 2, 1990.
`+ DepartmentofElectrical Engineering, Ruhr-Universitat Bochum, 4630 Bochum, Germany.
`713
`
`21
`
`OnePlus Ex. 1021.0021
`IPR2022-00048
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`1. Introduction. One important problem in linear algebra and digital signal pro-
`cessing is the singular value decomposition (SVD). Typical applications arise in beam-
`forming and direction finding, spectrum analysis, digital image processing,etc. [1]. Re-
`cently, there has been a massive interest in parallel architectures for computing SVD
`because of the high computational complexity of SVD, the growing importanceofreal-
`time signal processing, and the rapid advancesin very large scale integration ( VLSI) that
`make low-cost, high-density and fast processing memory devices available.
`There are different numerically stable methods for computing complete singular
`value and singular vector systems of dense matrices, for example, the Jacobi SVD method,
`the OR method, and the one-sided Hestenes method. For parallel implementations, the
`Jacobi SVD method is far superior in terms of simplicity, regularity, and local com-
`munications. Brent, Luk, and Van Loan have shown how the Jacobi SVD method with
`parallel ordering can be implemented by a two-dimensional systolic array [2], [3]. Various
`coordinate rotation digital computer (CORDIC) realizations ofthe SVD array have been
`reported by Cavallaro and Luk [4] and Delosme [5], [6].
`The Jacobi SVD method is based on, as commonforall two-sided approaches,
`applying a sequence of two-sided rotations to 2 X 2 submatrices ofthe original matrix.
`The computational complexity is thus determined by how to compute the two-sided
`rotations. In most previous works, a two-sided rotation is evaluated in a straightforward
`manner by four plane rotations, where two of them are applied from left to the two
`column vectors of the 2 * 2 submatrix and the other onesare applied from right to the
`row vectors, respectively. In the diagonal processing elements (PEs), additional operations
`for calculating rotation angles are required. This leads to an inhomogeneousarray ar-
`chitecture containing two different types of PEs.
`In this paper, we develop a two-plane rotation (TPR) method for computing two-
`sided rotations. We show that the above computational complexity can be reducedsig-
`nificantly because each two-sided rotation can be evaluated by only two plane rotations
`and a few additions. Moreover, the SVD array given by Brent and Luk becomes ho-
`mogeneouswith identical diagonal and off-diagonal PEs when CORDICprocessors are
`
`21
`
`OnePlus Ex. 1021.0021
`IPR2022-00048
`
`
`
`714
`
`B. YANG AND J. F. BOHME
`
`
`used. In a recent work [6], Delosmehas also indicated this possibility in connection
`with “trough rotations” independently. He has taken, however,a different approachthat
`is based on encoding the rotation angles. He hasstill required four plane rotations on
`
`the off-diagonal PEs while diagonal and off-diagonal operations can be overlapped.
`
`Ourpaperis organized asfollows. In § 2, we briefly reexamine Jacobi’s SVD method
`and Brent and Luk’s SVDarray. Then, we develop the TPR methodin § 3. The CORDIC
`
`algorithm is described in § 4, where in particular CORDICscaling correction techniques
`
`are discussed and examplesof scaling-corrected CORDIC sequencesare given.In § 5,a
`
`unified CORDIC SVD module for all PEs of the SVD array is presented. This module
`is comparedto those proposed by Cavallaro, Luk, and Delosmein§6. Finally, westress
`the applicability of the TPR method to several other problems.
`
`2. Jacobi SVD method. In this paper, we considerreal, square, and nonsymmetric
`matrices. Let M € R‘*” be a matrix of dimension N. The SVDis given by
`
`(1)
`
`M=U3V",
`
`
`where U € R**” and V € R*** are orthogonal matrices containing theleft and right
`singular vectors, and € R‘** is a diagonal matrix ofsingular values, respectively. The
`superscript 7 denotes matrix transpose. Based on an extension of the Jacobieigenvalue
`algorithm [7], Kogbetliantz [8] and Forsythe and Henrici [9] proposed to diagonalize
`M bya sequenceof two-sided rotations,
`
`(2)
`
`Mo=M,
`
`My.41= ULM, V;
`
`(k=0,1,2, +++).
`
`U,, and V; describe tworotationsin the (7, /)-plane (1 S i <j S N), wheretherotation -
`angles are chosen to annihilate the elements of MM, at the positions (i, /) and (J,i),
`
`m
`Usually, several sweeps are necessary to complete the SVD, where a sweepis a sequence
`
`of N(N — 1)/2 two-sided rotations according to a special ordering of the N(N — 1)/2
`
`different index pairs (7, /).
`For sequential computing on a uniprocessor system, possibly the most frequently
`used orderings are the cyclic orderings, namely, the cyclic row ordering
`
`
`
`(3)
`
`(2,J)=(1,2),C1,3), +++ C1), (2,3), +++ (25.4), +** CGV —-1,N)
`
`
`
`d
`
`(¢
`
`di
`
`(2
`el
`ge
`
`ar
`ar
`Sti
`
`OF
`
`ees
`
`
`
`
`
`or the equivalent cyclic column ordering. Sameh [10] and Schwiegelshohnand Thiee
`[11] have shown how to implementthe cyclic row ordering on a ring-connectedora
`mesh-connected processor array. Recently, a variety of parallel orderings havebeende.
`veloped. Luk and Park [12] have shownthatthese parallel orderings are essentially equi.
`alent to the cyclic orderings and thus share the same convergenceproperties.
`Brent and Luk havesuggested a particular parallel ordering and developed a squat
`systolic array consisting of [N/2]X [N/21PEs for implementing the Jacobi SVD method
`(Fig. 1). To do this, the matrix
`is partitioned into 2 X 2 submatrices. Each PEcontains
`one submatrix and performs a two-sided rotation
`
`
`
`
`
`
`
`(4)
`
`where
`
`(5)
`
`B= R(6,)’AR(62),
`
`= Qa;
`A=
`a2;
`
`a)2
`An?
`
`= by bi
`and B=
`br,
`br»
`
`22
`
`R(
`
`the
`
`
`.0022
`nerius EX.
`IPR2022-00048
`
`
`
`22
`
`OnePlus Ex. 1021.0022
`IPR2022-00048
`
`
`
`
`
`(6)
`
`Ro) =(
`
`cos@ sin@
`
`—sin@ cosé
`
`describes a plane rotation through theangle 6. Atfirst, the diagonal PEs (symbolized by
`adouble square in Fig. 1 ) generate the rotation angles to diagonalize the 2 x 2 submatrices
`(bj) = by; = 0) stored in them. This meansthat 6, and 4) are first calculated from the
`dements of A and then relation (4) is used to compute 5,; and b2.. Wecall this the
`generation mode. Then,the rotation anglesare senttoall off-diagonal PEs in the following
`way: the angles associated to theleft-side rotations propagate along the rows while the
`angles associated to the right-side rotations propagate along the columns. Once these
`angles are received, the off-diagonal PEs perform the two-sided rotations (4) on their
`stored data. Wecall this the rotation mode. Clearly, if we compute the rotation mode
`straightforwardly, we require four plane rotations. For the generation mode, additional
`operations for calculating 6; and @2 are required.
`3. TPR method for computing two-sided rotations. In order to develop the TPR
`method for computing two-sided rotations more efficiently, we first discuss the com-
`mutative properties of two special types, the rotation-type and the reflection-type, of
`2X 2 matrices. We define
`
`TAS
`
`REDUCED SVD COMPUTATIONS AND HOMOGENEOUS SVD ARRAY
`
`
`
`
`
`
`Fic. 1. The SVD array given by Brent and Luk.
`
`denote the submatrix before and after the two-sided rotation, respectively, and
`
`ols
`
`x.ver|
`
`
`
`and Mal" ”)
`
`y =x
`
` x.yer,
`
`The formeris called rotation-type because it has the same matrix structure as a 2 X 2
`plane rotation matrix. Similarly, the latter is called reflection-type because it has the
`same matrix structure as a 2 X 2 Givensreflection matrix [13]. Note that x and y must
`not be normalized to x? + y? = 1. Using the above definitions, the following results can
`be shown by some elementary manipulations.
`LEMMA1. IfA, €.@™ and A, € M™, then A\ Az = A2A\ € Me,
`LEMMA 2. IfA,€.@™ and A, € M™, then A\Ay = ATA, E M™,
`In particular, if we consider two plane rotations, we know the following.
`LEMMA 3. If R(0,) and R(@2) are plane rotations described by (6),
`R(0;)R(82) = R(O; + 62) and R(6,)"R(62) = R62 — 41).
`Now, we give a theorem describing the rotation mode of the TPR method.
`THEOREM. If the 2 X 2 matrix A andthe tworotation angles 6, and 62 aregiven,
`then the two-sided rotation (4) can be computed by two planerotations, ten additions,
`
`then
`
`
`
`23
`
`OnePlus Ex. 1021.0023
`IPR2022-00048
`
`23
`
`OnePlus Ex. 1021.0023
`IPR2022-00048
`
`
`
`716
`
`B. YANG AND J. F. BOHME
`
`andfour scalings by 3:
`(8)
`
`Di = (22+ a,;)/2,
`G1 = (2, — ay2)/2,
`6_=62—6,,
`
`(7)-R9(3)).
`
`i
`
`ty
`
`1
`
`(9)
`
`(10)
`
`(11)
`
`D2 = (22 — a1)/2,
`G2 = (21 + ay2)/2,
`0, =0.+6),
`r
`
`(7) -#00(2).
`
`ly
`
`a
`
`by = hth,
`byy=ri—fo,
`12
`1Th
`1
`L172
`by =r, +r.
`by, =t +h,
`Proof. Using (8), the matrix A can be reformulated as
`
`A=Ata(?! See oy
`N
`Pi
`42
`P2
`Clearly, R(6;), R(62) in (4) and A, are elements of .@™while Az belongs to .@™, This
`leads to the following reformulation of the matrix B by using Lemmas 1-3:
`B= R(0,)7AR(62)
`
`= R(6,)7A,R(62)+R(O,)7A>R(6>)
`
`= R(0,)7R(02)A;+ R(0,)7R(O2)7A>
`
`= R(0.—6,)A; + R(02+6;)7Ay
`
`{1
`
`Pi
`
`=R0(?" eRe( a
`_({"% 4 4. “rn
`3b
`ty
`ry
`b 1
`
`42
`
`P2
`
`
`
`This completes the proof.
`The generation mode of the TPR methodfollows directly from the abovetheorem, :
`COROLLARY. If the 2 X 2 matrix A is given, we can diagonalize A andcalculate’
`the corresponding rotation angles 0; and 0) by two Cartesian-to-polar coordinates con-
`versions, eight additions, andfour scalings by }:
`Di = (22 + @,)/2,
`D2 = (@x2— ay, )/2,
`1 = (2, — a12)/2,
`G2 = (21 + 12)/2,
`n=sign(p,)Vpi+gi,
`m=sign (p.)Vp3+q3,
`6_ = arctan (q:/p;),
`6, = arctan (g2/p>),
`6, = (0, —6_)/2,
`62 = (0, + 6_)/2,
`
`(12)
`(13)
`
`(14)
`
`(15)
`
`p18)
`inw
`(19)
`ceic
`Equ
`(20
`
`_
`
`
`
`by =ry+n.
`bi =r—-r,
`Proof. Regarding (11), b:2 = bo; = 0 is equivalent to t, = t = 0. Equation(13)
`follows then from (10). This completes the proof.
`In equation (13), we choose the rotation through the smaller angle. All vectors
`lyingin the first or the fourth quadrantare rotated onto the positive x-axis, andall vectors
`lying in the second and the third quadrant are rotated onto the negative x-axis, For
`vectors on the y-axis, the rotation direction is arbitrary. Thus, the generated rotation
`
`
`
`oA
`
`
`
`OnePlus Ex.
`IPR2022-00048
`
`24
`
`OnePlus Ex. 1021.0024
`IPR2022-00048
`
`
`
`REDUCED SVD COMPUTATIONS AND HOMOGENEOUS SVD ARRAY
`
`717
`
`angles 0. and 0, satisfy |@_|,
`(16)
`
`|6,| < 90°. This results in
`|0,|S90°
`and
`|6,| $909,
`
`due to (14).
`Equation (16) is important with respect to the convergence of the Jacobi SVD
`method. Forsythe and Henrici [9] have proven the convergence for cyclic orderings if
`the rotation angles 6, and 6, are restricted to a closed interval inside the open interval
`(-90°, 90°). They have also demonstrated that this condition mayfail to hold, i.e., 6;
`
`and 6. may be +90°, if the off-diagonal elements b,. and b2; in (5) have to be exactly
`annihilated. As a remedy, they suggested an under- or overrotation by computing the
`
`two-sided rotation (4) with angles (1 — y)6,; and (1 — y)@2 (—1 < y < 1) and proved
`
`its convergence. In practice, however, the finite machine accuracy in the real arithmetic
`
`allows only an approximative computation of the rotation angles and implies under- or
`
`overrotations. So the Jacobi SVD method converges without using under- or overrotations
`
`asshown by the experimental results of Brent, Luk, and Van Loan [3]. In case ofCORDIC
`implementations, the effect of implicit under- or overrotations is more apparent. The
`
`angles +90° can neverbe exactly calculated because of the limited angle resolution arc-
`tan(2~”) of the CORDICalgorithm, where p denotes the mantissa length.
`
`4. The CORDICalgorithm. In the previous section, we have seen that the main
`
`operations of the TPR-methodare plane rotations and Cartesian-to-polar coordinates
`conversions. These operations can be carried out by multiplier-adder-based processors
`
`supported by software or special hardware units. An alternative approach is the use of
`
`dedicated processors that usually map algorithms moreeffectively to hardware. The
`
`CORDIC processoris such a powerful onefor calculating trigonometric functions.
`
`The CORDICalgorithm wasoriginally designed by Volder [14] as an iterative pro-
`
`cedure for computing plane rotations and Cartesian-to-polar coordinates conversions.It
`was later generalized and unified by Walther [15], enabling a CORDIC processor to
`
`calculate more functions, including hyperbolic functions, as well as multiplications and
`
`divisions. In the following, we consider Volder’s CORDICalgorithm because onlytrig-
`onometric functions are involved in SVD applications.
`The CORDICalgorithm consists of iterative shift-add operations on a three-com-
`ponent vector,
`
`
`
`
`
`(18)
`
`Zis1 = 2) — €0;0;
`
`(0 <6;< ljo,=+lje=+1;1=0,1,°::,n-—1),
`
`6; = tan (a;)=2-.
`
`k;
`
`=Vi+8,
`
`
`in which the iteration stepsize 6, is defined by
`
`(19)
`
`The set of integers {.S(i)} parametrizing the iterations is called CORDIC sequence.
`Equation (17) can be interpreted, except for a scaling factor of
`
`
`
`(20)
`- cos (a;)
`
`asa rotation of (x;, y;)’ through the angle a;, where the sign o; = +1 gives the rotation
`direction. After 7 iterations, the results are given by
`
`a
`
`
`
`(22)
`
`x
`
`Vn
`
`fglane
`
`cosa —sina)\/
`
`sin @
`
`cos a/\
`
`Xo
`
`eee)
`
`Yo
`
`Zn = Zo—e0,,
`
`25
`
`OnePlus Ex. 1021.0025
`IPR2022-00048
`
`
`
`(17) fr + ’ 7 (® — o6iVi\ |
`
`
`
`
`
`
`
`1
`
`cos(a;) —a; Sin (@;) a)
`
`
`
`Vi+1 cos (a;)\o; sin (a;)yi + 0;6;x;} cos (a) /\y;)’
`
`25
`
`OnePlus Ex. 1021.0025
`IPR2022-00048
`
`
`
`718
`
`B. YANG AND J. F. BOHME
`
`with the overall scaling factor K = |], k; andthetotal rotation angle a = 2; o;a;. Now,
`if the CORDIC sequencesatisfies the following convergence condition
`n~—l
`a- D>, wSan-s
`jJ=it+il
`
`(i=0,1, «-* ,n—-2),
`
`(23)
`
`we can choosethe sign parameter
`
`(24)
`
`—sign (x;y;)
`=).
`sign (e€Z;)
`
`fory,—>0,
`
`for z,—> 0
`
`to force y, or Z, to zero, provided that the input data x9, yo, and Zo lie in the conver-
`gence region
`
`oT
`
`fory,—0,
`
`for z,—> 0.
`
`
`
`
`In this way, two different types of CORDIC trigonometric functions can be computed
`(Table 1). In the mode y,, > 0, the Cartesian coordinate (Xo, yo) of a plane vector is
`converted to its polar representation, where the parameter e = +1 deter